Proof Conclusion & Layer Thresholds
Synthesizing interior arc capacity bounds, the supply vs. demand collapse threshold $i \le \frac{\delta}{3}$, forced terminal Seymour vertices, and algorithmic complexity.
Graph Capacity Bounds
Combining required interior arcs $|R_i| \cdot i$ with maximum off-diagonal capacity $\binom{|R_i|}{2}$.
Threshold $i = \lceil \frac{\delta}{3} \rceil$
When depth exceeds $\delta/3$, capacity collapses and forces Seymour vertices.
Terminal Seymour & $O(|V|+|E|)$
All nodes in terminal layer $R_k$ are Seymour; Graph Level Order executes in linear time.
Interior Capacity vs. Demand Inequality
By Load Balance Theorem and Iterative Corollary, interior degree $i$ requires:
Off-diagonal oriented pair capacity in layer $R_i$ is bounded above by:
Intersection of Supply and Demand
|R_i| ≥ 2i + 1
Minimum nodes required to support $i$ interior cycles.
|R_i| = δ - i + 1
Available node capacity at layer distance $i$.
Forced Multiple Seymour Vertices
Let $G \in \mathcal{O}$ be an oriented graph with minimum out-degree $\delta$, and let $R_i$ be the last, most dense rooted neighborhood at distance $k = \lceil \delta / 3 \rceil$. Then EVERY node in $R_i$ is a Seymour vertex.
Terminal Neighborhood Size Dynamics
Any oriented graph $G \in \mathcal{O}$ in an MCE with $>3$ nodes reaches its last rooted neighborhood at distance $\lceil \delta / 3 \rceil$. The size of this terminal layer is:
This is an integer $>1$ as long as $\delta > 1.5$ (which is necessary for cycles to exist in $G$), guaranteeing that multiple Seymour vertices accumulate simultaneously in the terminal layer.
Algorithm & Complexity Theory
Let $G$ be an oriented graph. The Graph Level Order algorithm runs in optimal linear time:
Breadth-First Search traversal visits each vertex $v \in V$ and explores each outgoing arc $e \in E$ exactly once, bounding coordinate assignments to $\mathcal{O}(|V| + |E|)$.
Lexicographical sorting over neighborhood sets operates efficiently alongside the BFS queue, preserving overall linear time complexity.