Special Case Analysis

MCE Dynamics in Graphs Without Back Arcs

Analyzing out-degree distributions, layer size decay $|R_k| = \delta - k + 1$, and exact interior arc bounds under the exclusion of back arcs.

Lemma 1

Degree Partition

Strict disjoint partition into interior and exterior out-neighbors.

Theorem 1 & 2

Neighborhood Decrease

Inductive size decay $|R_k| = \delta - k + 1$ and interior lower bound $k+1$.

Lemmas 2 & 3

Exact Interior Degree

Seymour force constraints and minimality equality $\text{int}(u_k, v_{k+1}) = k+1$.

Lemma 1 (nodepartition)

Disjoint Degree Partition

Lemma 1 (Degree Partition) label: nodepartition

Let $u_i \in R_i$ and let $v_{i+1} \in R_{i+1}$ be vertices of an MCE, with $u_i \to v_{i+1} \in G$. Then the out-neighborhood of $v_{i+1}$ admits the disjoint partition:

$$N^+(v_{i+1}) = \text{int}(u_i, v_{i+1}) \;\dot{\cup}\; \text{ext}(u_i, v_{i+1})$$

Proof Outline

Every out-neighbor of $v_{i+1}$ lies in exactly one rooted neighborhood $R_j$.
Exclusion of back arcs restricts outgoing targets to layers $R_{i+1}$ or $R_{i+2}$.
If $x \in R_{i+2} \implies x \in \text{ext}(u_i, v_{i+1})$. If $x \in R_{i+1} \implies x \in \text{int}(u_i, v_{i+1})$.
Distance layers are pairwise disjoint, guaranteeing a clean partition of $N^+(v_{i+1})$.

Theorem 1 (layer_size)

Neighborhood Size Formula: $|R_k| = \delta - k + 1$

Let $G \in \mathcal{O}$ be an MCE with MDN $v_0$ and rooted neighborhoods $R_0, R_1, \ldots, R_k$. Suppose all nodes are non-Seymour. Then for all $i \ge 0$:

$$|R_k| = \delta - k + 1$$

Base Case ($i=0$)

$R_0 = \{v_0\}$. For $v_1 \in R_1$, sending $> \delta$ exterior neighbors makes $v_0$ Seymour. Pigeonhole principle forces at least 1 interior arc. MCE density minimality forces exactly 1 interior arc and $\delta - 1$ exterior arcs.

Inductive Step ($k \to k+1$)

With $|R_k| = \delta - k + 1$, sending $> \delta - k + 1$ exterior arcs makes $u_k$ Seymour. Thus $v_{k+1}$ needs $\ge k+1$ interior arcs, leaving at most $\delta - (k+1)$ exterior arcs to $R_{k+2}$.

Visual Layer Decay

Iterated Decrease in Second Neighborhoods

As distance from root increases, available layer capacity decreases linearly: $|R_k| = \delta - (k-1)$.

R_1 (δ)

R_2

R_3

R_j

R_5

R_6

u_i

Structural Consequence: Shrinking layer capacities force nodes further from the root to form more intra-layer (interior) connections to satisfy minimum out-degree bounds.

Theorem 2 (Interior Bound)

Lower Bound on Interior Neighbors

Let $G \in \mathcal{O}$ be an MCE represented by rooted neighborhoods $R_0, R_1, \ldots, R_n$ with layer sizes $|R_i| = \delta - i + 1$. For each node $u \in R_k$ and child $v \in R_{k+1}$ ($u \to v \in G$):

$$\text{int}(u, v) \ge k + 1$$

Derivation Summary

To keep parent $u_k$ non-Seymour, at least $\delta - (k+1) + 1$ nodes are required in layer $R_{k+1}$. By the pigeonhole principle, $v_{k+1}$ cannot exceed $\delta - (k+2) + 1$ exterior arcs, forcing:

$$\text{ext}(u, v) \le \delta - (k+1) \implies \text{int}(u, v) \ge k+1$$

Lemma 2 (Seymour Constraint)

Extra Exterior Arcs Produce Seymour Vertices

Lemma 2 Seymour Threshold

If the number of exterior neighbors associated with $(u_k, v_{k+1})$ bounds $u_k$'s out-degree from below:

$$|N^+(u_k)| \le |\text{ext}(u_k, v_{k+1})|$$

Then $u_k$ is guaranteed to be a Seymour vertex: $|N^+(u_k)| \le |N^{++}(u_k)|$.

Proof Chain

$$\text{ext}(u_k, v_{k+1}) \subseteq N^{++}(u_k) \implies |\text{ext}(u_k, v_{k+1})| \le |N^{++}(u_k)|$$

$$|N^+(u_k)| \le |\text{ext}(u_k, v_{k+1})| \le |N^{++}(u_k)| \implies |N^+(u_k)| \le |N^{++}(u_k)|$$

Lemma 3 (intdeg)

Exact Interior Degree: $\text{int}(u_k, v_{k+1}) = k+1$

Lemma 3 (MCE Interior Degree) label: intdeg

Let $G \in \mathcal{O}$ be a counterexample. Suppose $u_k \in R_k \to v_{k+1} \in R_{k+1}$ is a parent-child pair. Then its interior degree is precisely:

$$\text{int}(u_k, v_{k+1}) = k+1$$

Proof by Contradiction

Suppose $\text{int}(u_k, v_{k+1}) > k+1$. Then the pair is over-connected, violating the minimal neighborhood density metric required for an MCE. Removing an excess interior arc yields a strictly smaller counterexample, contradicting MCE minimality. Combining with $\text{int}(u_k, v_{k+1}) \ge k+1$ forces exact equality.

MCE Analysis without Back Arcs