Graph Level Order & Structural Theorems
Connecting graph level order vocabulary to structural equivalence relations, quotient hyper-node graphs, 8-case transitive triangle classifications, and Seymour diamond resolutions.
Quotient Hyper-Graph
Rooted degree-preserving equivalence relation $\sim$ collapsing layers to hyper-nodes.
Hierholzer & Triangles
$k$ disjoint cycles in $R_k$ and 8-case classification of load-balancing transitive triangles.
Seymour Resolution
Set-union evaluation over exterior neighbors resolving double-counting ambiguities.
Rooted Neighborhood Equivalence Relation
Let $G$ be a Minimum Counterexample (MCE). Every vertex within a rooted neighborhood $R_k$ is indistinguishable under the rooted degree-preserving mapping $\sim$. The resulting quotient graph $G/\sim$ is a well-defined hyper-node graph that preserves the out-degree and non-Seymour status of $G$.
Proof Breakdown
- Identical Parents: $v_k, w_k \in R_k$ share identical distance and parent sets by BFS-Lex ordering.
- Degree Partition & Load Balance: $v_k$ and $w_k$ have identical interior degrees of $k$, with all interior arcs forming forward-facing load-balancing transitive triangles.
- Exterior Lineage: Exclusion of back arcs forces identical exterior neighbor sets.
- Isomorphism: $G[R(v_k)] \cong G[R(w_k)]$, collapsing $R_k$ into equivalence classes and proving $G/\sim$ is a well-defined quotient graph.
Hyper-Graph vs. Line Graph Distinction
The rooted degree equivalence $\sim_k$ partitions $V$ into equivalence classes $R_0, R_1, \ldots, R_m$. Each class $R_k$ collapsed to a single hyper-node forms a directed path on $m+1$ hyper-nodes.
The original graph $G$ is not a line graph or a simple path. It retains its full original vertex set $V(G)$ and complete arc set $E(G)$.
$G$ preserves its internal cycle structure and density interactions within each individual rooted neighborhood layer $R_k$.
Disjoint Cycles via Hierholzer's Algorithm
Let $G=(V,E)$ be an MCE to the SSNC with root $v_0$ and let $R_k$ be a rooted neighborhood at distance $k$ from $v_0$. Because every node has an interior degree of $k$ in $R_k$, Hierholzer's Algorithm will find at least $k$ disjoint cycles in $R_k$.
The exact interior degree $\text{int}(u_k, v_{k+1}) = k$ guarantees an Eulerian or regular sub-structure within layer $R_k$, providing the required degree balance for cycle decompositions.
Classification of Load-Balancing Triangles
| Case | Labels | Possible? | Structural Reason / Exclusion |
|---|---|---|---|
| 1 | 3I | No (in MCE) | All Intra-layer; contains extra interior arc, violating load-balance. |
| 2, 4 | 1B2I / 1F2I | No | Symmetric Arcs impossibility. |
| 3 | 2B1I | Excluded | $x,y \in R_i, z \in R_{i+1}$. Excluded by back arc reduction. |
| 5 | 1F1B1I | Excluded | $x,y \in R_i, z \in R_{i+1}$. Excluded by back arc reduction. |
| 6 | 1F2B | Excluded | $x \in R_i, y \in R_{i+1}, z \in R_{i+2}$. Excluded by back arc reduction. |
| 7 | 2F1I | UNIQUE YES | $x \in R_i, y,z \in R_{i+1}$. Load-Balancing Triangle! |
| 8 | 2F1B | No | Cannot form a closed transitive triangle. |
Resolution of Seymour Diamonds
Let $G \in \mathcal{O}$ be a Graph Level Order containing a Seymour diamond. Then the ambiguity is resolved via exterior neighbors.
Proof Breakdown
Assume $G$ has a Seymour diamond $(u_i, v_{i+1}, w_{i+1}, y_{i+2})$. By reduction theorems:
Because exterior neighbors are evaluated as sets (unions) rather than arithmetic sums, any node $y_{i+2}$ reached by multiple length-2 paths is counted exactly once in $N^{++}(u_i)$, completely eliminating double-counting.