Disconnected Back Neighbors
Analyzing the impossibility of disconnected back arcs in an MCE through local density constraints, disjoint neighbor bounds, and well-founded sequence termination.
$\delta$-Regularity
Exclusion of back arcs forces initial nodes to satisfy exact $\delta$-regularity.
Disjoint Back Arcs
When $N^+(v) \cap N^+(u) = \emptyset$, $u$ is forced to be a Seymour vertex.
Loop Closure
Recursive back-arc chains are well-founded and force Seymour loop closure.
Density Bounds & $\delta$-Regularity
If child $v$ possesses an excess exterior arc, it lands in $N^{++}(u)$, forcing $|N^{++}(u)| \ge |N^+(u)|$ and instantly turning parent $u$ into a Seymour vertex.
If a node takes on too many interior arcs, it exceeds the local density threshold of subgraph $R_i$, violating MCE density minimization.
Implication for Disconnected Back Arcs
Prior to the first disconnected back neighbor, nodes are strictly $\delta$-regular. Analyzing the first back arc $u_k \to v_{k+1} \to w_j$ ($j \le k-1$) splits into two exhaustive cases:
Seymour Property under Disjoint Back Arcs
Let $G$ be an MCE graph, and let $u_k, v_{k+1} \in V(G)$ with $v_{k+1} \in N^+(u_k)$. If out-neighbors are completely disjoint ($N^+(v_{k+1}) \cap N^+(u_k) = \emptyset$) and degree bounds satisfy $|N^+(u_k)| \le \delta \le |N^+(v_{k+1})|$, then $u_k$ is a Seymour vertex:
Proof Breakdown
- Every back neighbor $z_j \in N^+(v_{k+1})$ reaches $u_k$ in 2 steps: $u_k \to v_{k+1} \to z_j$.
- By anti-symmetry, $z_j \neq u_k$. By disjointness, $z_j \notin N^+(u_k)$. Thus $N^+(v_{k+1}) \subseteq N^{++}(u_k)$.
- Regularity implies $|N^+(u_k)| = |N^+(z_j)| = \delta$, chaining to: $|N^+(u_k)| = \delta = |N^+(v_{k+1})| \le |N^{++}(u_k)|$.
Termination & Loop Closure of Back-Arc Chains
Let $G$ be an MCE under the BFS-Lex coordinate system. Any recursive propagation of back-arcs forms a well-founded sequence that must terminate by closing a loop, thereby forcing a Seymour vertex.
A back-arc sequence $\langle c_0, c_1, \dots \rangle$ drops $\ge 2$ layers each step ($\text{dist}(c_{i+1}) + 2 \le \text{dist}(c_i)$).
BFS-Lex guarantees a minimal node $c_m$ initiating the earliest back-arc. No earlier back-arc exists.
The chain must close a loop into $N^+(u_k)$, adding length-2 paths and forcing $|N^{++}(u_k)| \ge |N^+(u_k)|$.