Connected Back Neighbors
Analyzing the first connected back arc case in an MCE under prior $\delta$-regularity and proving its impossibility via bi-directional arc violations.
Prior Regularity
Exclusion of disconnected back arcs forces initial layers to achieve full regularity.
Full Layer Saturation
$\text{ext}(u_k, v_{k+1}) = \delta - (k+1)$ forces every node in $R_{k+1}$ to parent all nodes in $R_{k+2}$.
Bi-Directional Conflict
A connected back arc creates $z \to y$ alongside $y \to z$, violating orientation.
Arriving at the First Connected Back Arc
Excluding back arcs establishes exact $\delta$-regularity and precise layer decay $|R_k| = \delta - k + 1$ in the minimum counterexample.
Previous theorems prove disconnected back arcs cannot exist (they either force disjoint Seymour nodes or well-founded loop closure).
The Core Question
When we evaluate the remaining case of connected back neighbors ($u \to v \to w$ where target $w$ sits in the adjacent preceding layer $R_i$), we must ask: Where can the first connected back neighbor occur in a BFS-Lex well-ordering?
Impossibility of Connected Back Neighbors
Let $G \in \mathcal{O}$ be an MCE represented by rooted neighborhoods $R_0, R_1, \ldots, R_k$. Then the first connected back neighbor in $G$ cannot exist.
Proof Breakdown
- Disconnected back neighbors are excluded by structural constraints.
- Exact interior degree is established as $\text{int}(u_k, v_{k+1}) = k + 1$.
- Combining these yields exact exterior capacity: $\text{ext}(u_k, v_{k+1}) = \delta - (k+1)$.
- This forces every node $y_{k+1} \in R_{k+1}$ to be a parent to every node $z_{k+2} \in R_{k+2}$.
The Bi-Directional Arc Violation
Full exterior saturation requires that for any $y_{k+1} \in R_{k+1}$ and $z_{k+2} \in R_{k+2}$, there must exist a forward arc:
Suppose there exists a connected back neighbor from $R_{k+2}$ back to $R_{k+1}$, i.e., $z_i \in R_{k+2}$ such that:
This creates a bi-directional arc pair ($y_{k+1} \to z_i$ and $z_i \to y_{k+1}$), which directly violates the defining property of an oriented graph ($G \in \mathcal{O}$).