Lemmas

Lemmas and Proofs

This page provides a quick reference to all the lemmas and their corresponding proofs from the paper. As you go through them, you’ll also find D3 visualizations illustrating each concept. Click on the visualizations for interactive views and better understanding.

Use Social Media Info?

content: Suppose that the minimum out-degree node $v_0$ in the oriented graph $G$ has an out-degree less than 3. Then $v_0$'s out-degree will at least double.
proof: We will consider the cases where $d^+(v_0)=0$, $1$, and $2$.

Case 1: Assume that $d^+(v_0)=0$. In this case $v_0$ has no out-neighbors, i.e, $|N^+(v_0)|=0$. Since $v_0$ has no out-neighbors, it also has no second out-neighbors. This means that $|N^{++}(v_0)|=0$. This will imply that $|N^{++}(v_0)| = |N^+(v_0)|$, which will make $v_0$ a degree-doubling node.

Case 2: Assume that $d^+(v_0)=1$. Here, $v_0$ has a unique out-neighbor. Let $v_1$ be that unique out-neighbor of $v_0$. We know that $|N^+(v_0)|=1$. Because $v_0$ is a minimum out-degree node, the out-degree of $v_1$ must be at least 1. This means that $v_1$ must have an out-neighbor. This neighbor cannot be $v_0$ since this graph is oriented and $v_0$ already has an arc to $v_1$. This means that it must be some node $v_2$, which will be a second out-neighbor of $v_0$. So we know that $|N^{++}(v_0)| \geq 1$. Thus we have that $|N^{++}(v_0)| \geq |N^+(v_0)|$ and $v_0$ is a degree-doubling node.

Case 3: Assume that $d^+(v_0) = 2$. Let's call the out-neighbors of $v_0$, $v_1$ and $v_2$, where $|N^+(v_0)|=2$. We know that $d^+(v_1) \geq 2$ and $d^+(v_2) \geq 2$ since $v_0$ is a minimum out-degree node. Consider the induced subgraph $G[v_1,v_2]$. At most one arc can exist in an oriented graph of size 2 because oriented graphs do not allow for symmetric arcs. So we know that there is at most one arc between $v_1$ and $v_2$ in this induced subgraph. This means that $v_1$ or $v_2$ will have at least two arcs outside of $G[v_1,v_2]$. Neither $v_1$ or $v_2$ can relate to $v_0$ since $G$ is an oriented graph and $v_0 \to v_1 \in G$ and $v_0 \to v_2 \in G$. We can define the nodes $v_3$ and $v_4$ as the two out-neighbors of $v_1$ not in ${v_0, v_1, v_2}$. This means that $v_0$ will have $v_3$ and $v_4$ as second neighbors. Hence, $v_0$ will have at least two second out-neighbors�$v_3$ and $v_4$. Thus $|N^{++}(v_0)| \geq 2$ and $|N^{++}(v_0)| \geq |N^+(v_0)|$, and $v_0$ is a degree-doubling node.

Therefore, in all cases, $v_0$ is found to be a degree-doubling node when its minimum degree is less than 3.
label: Minimum Out-Degree $<$ 3

content: Suppose a minimum out-degree node $v_0$ in an oriented graph has an out-degree of 3. Suppose also that at least one of $v_0$'s neighbors has out-degree 0 in its neighbor induced subgraph. Then the out-degree of $v_0$ will at least double in $G^2$.
proof: Assume $d^+(v_0)=3$, and let $v_1, v_2, v_3$ be the out-neighbors of $v_0$. We see then that $|N^+(v_0)|=3$. Consider the neighbor induced subgraph $G[v_1, v_2, v_3]$.

Assume that $v_1$, which is a neighbor of $v_0$ has out-degree 0 in $G[v_1, v_2, v_3]$. This means that $v_1 \to v_2 \notin G[v_1, v_2, v_3]$ and $v_1 \to v_3 \notin G[v_1, v_2, v_3]$. Since $v_0$ is a minimum out-degree node with out-degree 3, we know that $v_1$ must have out-degree at least 3. So $v_1$ must connect to at least 3 out-neighbors outside of $\{v_1, v_2, v_3\}$. Since $v_0 \to v_1 \in G$, we know that $v_1 \to v_0 \notin G$ by the oriented property of $G$. This means that $v_1$ must connect to at least three other nodes $v_4, v_5, v_6$. So we have $|N^+_G(v_1)| \geq 3$. The nodes $v_4, v_5, v_6$ are not in $G[v_1, v_2, v_3]$ and are not equal to $v_0$, so they are outside $G[v_0, v_1, v_2, v_3]$.

This means that these first out-neighbors of $v_1$ are second out-neighbors of $v_0$, so we have that $|N^{++}_{G}(v_0)| \geq 3$. We can simplify this and say that $|N^{++}(v_0)| \geq |N^+(v_0)|$. This means that $v_0$ is a degree-doubling node. Hence, $v_0$ must be a degree-doubling node, contradicting the assumption that such a node could exist in a minimal counterexample.
label: Minimum Out-Degree 3 with Neighbor Out-Degree 0 in the Neighbor Induced Subgraph

content: Assume that in an oriented graph $G$, the minimal out-degree node $v_0$ has an out-degree of 3. Additionally, suppose that in the induced subgraph of $v_0$'s out-neighbors, every neighbor has an out-degree of 1. Then the out-degree of $v_0$ or one of its neighbors will be a degree-doubling node.
proof: Assume $d^+(v_0)=3$. Let $v_1, v_2, v_3$ be the out-neighbors of $v_0$. Then $|N^+(v_0)|=3 $. We know that $d^+(v_i)\geq 3$ for each $v_i \in \{v_1,v_2,v_3\}$. Let $G[v_1,v_2,v_3]$ represent the induced subgraph by $v_1,v_2,v_3$.

We can reason that if any of $v_1,$ $v_2,$ or $v_3$ has an out-degree greater than 3, $v_0$ will have a larger second out-neighborhood than its first out-neighborhood, making it a degree-doubling node. Therefore, assume that all three nodes have an out-degree of exactly 3 in $G$. $|N^+(v_i)|=3$.

Similarly, by Lemma (Minimum Out-Degree 3 with Neighbor Out-Degree 0), We see that if any of the three first out-neighbors of $v_0$ does not have any first out-neighbors of $v_0$ as an out-neighbor, then $v_0$ has its degree doubled.

To prevent $v_0$ from being a degree-doubling node, each of the first out-neighbors of $v_0$ needs to have another first out-neighbor of $v_0$ as an out-neighbor. What this means is that for those nodes that are first out-neighbors of $v_0$, we have $|N^+_{G - G[v_1, v_2, v_3]}(v_i)|=2$.

This reduces the situation to Case 3 in Lemma (Minimum Out-Degree $<$ 3), where $v_1$ acts similarly to how $v_0$ did in that case. There is at most one arc between $v_4$ and $v_5$. We will say that $v_4$ has three additional out-neighbors, $v_6, v_7$, and $v_8$, with $v_4$ having degree zero in $G[v_4, v_5]$. Then $|N^+(v_4)|=3$. These three neighbors of $v_4$ are second out-neighbors of $v_1$, giving us $|N^{++}(v_1)|=3$. Thus we have the following equality, $|N^{++}(v_1)|=|N^+(v_1)|=3$, making $v_1$ a degree-doubling node.

Hence, $v_1$ must be a degree-doubling node, contradicting the assumption that such a node could exist in a minimal counterexample.
label: Minimum Out-Degree 3 with Neighbors 1 in the Neighbor Induced Subgraph

content: For any $v \in R_{i+1}$ with parent $u \in R_i$, the out-neighbors of $v$ can be partitioned as: \[ N^+(v) = \text{int}(u,v) \cup \text{ext}(u,v) \cup \text{back}(v) \] where the three sets are pairwise disjoint.
proof: Let $v \in R_{i+1}$ be a node with parent $u \in R_i$. We have defined the following three sets for any out-neighbor $w \in N^+(v)$:

$\text{back}(v) = \{w \in N^+(v) \mid \text{dist}(v_0, w) < \text{dist}(v_0, v)\}$
$\text{int}(u,v) = \{w \in N^+(v) \mid \text{dist}(v_0, w) = \text{dist}(v_0, v) \land u \to w \in G\}$
$\text{ext}(u,v) = \{w \in N^+(v) \mid (\text{dist}(v_0, w) = \text{dist}(v_0, v) \land u \to w \notin G) \lor (\text{dist}(v_0, w) > \text{dist}(v_0, v))\}$

We now show that these three sets form a partition of $N^+(v)$. Let $w \in N^+(v)$. The distance from $v_0$ to $w$, $\text{dist}(v_0, w) < \text{dist}(v_0, v)$, $\text{dist}(v_0, w) = \text{dist}(v_0, v)$, or $\text{dist}(v_0, w) > \text{dist}(v_0, v)$. This gives us three exhaustive and mutually exclusive cases for each $w \in N^+(v)$.

Case 1: $\text{dist}(v_0, w) < \text{dist}(v_0, v)$ By definition, $w \in \text{back}(v)$. Such an arc $v \to w$ is a back arc in the rooted neighborhood structure. Since its distance from $v_0$ is less than $\text{dist}(v_0, v)$, it cannot satisfy the conditions for $\text{int}(u,v)$ or $\text{ext}(u,v)$.

Case 2: $\text{dist}(v_0, w) = \text{dist}(v_0, v)$ In this case, $w$ is in the same rooted neighborhood $R_{i+1}$ as $v$. We consider the relationship between $u$ (the parent of $v$ in $R_i$) and $w$:

If $u \to w \in G$. This means $w$ is an out-neighbor of $v$ within the same layer, and also a direct out-neighbor of $v$'s parent $u$. So $w \in \text{int}(u,v)$
If $u \to w \notin G$. This means $w$ is an out-neighbor of $v$ within the same layer, but not a direct out-neighbor of $u$. So $w \in \text{ext}(u,v)$

These two sub-cases are mutually exclusive, so $w$ is uniquely assigned.

Case 3:. $\text{dist}(v_0, w) > \text{dist}(v_0, v)$ Since $v \to w \in G$ is an arc, and we are in a shortest-path graph from $v_0$, the only possible distance relationship for $w$ to be greater than $v$'s distance is $\text{dist}(v_0, w) = \text{dist}(v_0, v) + 1$. This implies $w \in R_{i+2}$. Since $u \in R_i$ and $w \in R_{i+2}$, there cannot be a direct arc $u \to w \in G$ in a shortest-path graph (as this would imply $\text{dist}(v_0, w) = \text{dist}(v_0, u) + 1 = i+1$, contradicting $\text{dist}(v_0, w) = i+2)$. Thus, $u \to w \notin G$. By definition, $w \in \text{ext}(u,v)$.

In every exhaustive case, we were able to show that $w$ belongs to exactly one of the sets $\text{int}(u,v)$, $\text{ext}(u,v)$, or $\text{back}(v)$. Therefore, these three sets form a pairwise disjoint partition of $N^+(v)$.
label: Partition of Node's Degree

content: Suppose we have an oriented graph $ G $, with minimum out-degree node $ v_0 $. Then, every node $ x $ in the neighboring rooted neighborhood $ R_1 $ must have an interior degree of at least 1. That is, for $ x \in R_1 $, \[ |\text{int}(v_0, x)| \geq 1. \]
proof: By definition, a node satisfies the Decreasing Neighborhood Sequence Property if \[ |N^+(x)| > |N^{++}(x)|. \] By the definition of an interior arc, \[ \text{int}(v_0, x) = N^+(v_0) \cap N^+(x) \] A node $x \in R_1$, will have exterior out-neighbors in $R_2$, making them second out-neighbors of $v_0$. If $x$ has zero interior arcs, then $x$ must have $\delta = d^+(v_0)$ exterior arcs. This means that the size of $v_0$'s second neighborhood, $|N^{++}(v_0)|$ would be at least $|N^+(v_0)|$, violating the DNSP condition for $v_0$. This implies that $x$ must have at least one interior arc to another node in $R_1$. By definition, $v_0$ has $d^+(v_0)$ first out-neighbors. This means that \[ N^{++}(v_0) \geq N^+(v_0). \] To avoid this doubling of $v_0$, $x$ must connect to at least one interior arc. This means that the interior degree of $x$ with respect to $v_0$ must satisfy \[ |\text{int}(v_0, x)| \geq 1 \] This is true for the out-neighbors of every node in $R_1$. This ensures that every node in $R_1$ has an interior degree of at least one. Hence, every node $x \in R_1$ satisfies \[|\text{int}(v_0,x)| \geq 1.\] Thus, for all $x \in R_1$, \[ |\text{int}(v_0, x)| \geq 1. \]
label: Interior Load Balancing Lemma

content: Let $G = (V, E)$ be an oriented graph and $u \in V(G)$. Suppose that for every $x \in N^+(u)$, there exists a $v \in N^+(u)$ such that $(u, v) \in E$ and $(v, x) \in E$. Then: \[ N^+(u) = \bigcup_{v \in N^+(u)} \text{int}(u, v) \]
proof: Recall that $\text{int}(u, v) = N^+(u) \cap N^+(v)$ for any $v \in N^+(u)$, where $u$ us a parent of $v$.

First, let $x \in N^+(u)$. By the premise, there exists $v \in N^+(u)$ such that $(u, v) \in E$ and $(v, x) \in E$. Thus, $x \in N^+(v)$, and $x \in \text{int}(u, v)$. Hence, $N^+(u) \subseteq \bigcup_{v \in N^+(u)} \text{int}(u, v)$.

Conversely, if $x \in \bigcup_{v \in N^+(u)} \text{int}(u, v)$, then there exists $v \in N^+(u)$ such that $x \in \text{int}(u, v)$. Therefore, $x \in N^+(u)$, and $\bigcup_{v \in N^+(u)} \text{int}(u, v) \subseteq N^+(u)$.

Combining both inclusions, we conclude $N^+(u) = \bigcup_{v \in N^+(u)} \text{int}(u, v)$.
label: Interior Cover Lemma

content: Suppose we have an oriented graph $G$. If $ x $ in rooted neighborhood $ R_i$ has the Decreasing Neighborhood Sequence Property, then for all $y \in N^+(x), |\text{ext}(x, y)| < d^+(x)$. That is, for any out-neighbor $y$ of $x$, the number of exterior out-neighbors of $x$ which are reached through $y$ must be less than the out-degree of $x$.
proof: Assume, for the sake of contradiction, that there is a node $ y \in N^+(x) $ such that $ |\text{ext}(x, y)| \geq d^+(x) $. By definition, $ \text{ext}(x, y) = N^{++}(x) \cap N^+(y)$. Thus, \[ |\text{ext}(x, y)| \subseteq N^{++}(x). \] Then: \[ |N^{++}(x)| \geq |N^+(x)| \geq d^+(x) \] This means that the out-degree of $ x $ at least doubles on the graph $ G^2 $. This contradicts the assumption that $ x $ has the DNSP. This must be true for all $x$ in $G$, so we conclude that for all $y \in N^+(x)$, the number of exterior connections $ |\text{ext}(x, y)| $ must be strictly less than $ d^+(x) $.
label: Exterior Load Balancing Lemma

content: Let $ G = (V, E) $ be a graph, and let $ u \in V $. Suppose that for every vertex $x$ at distance two from $u$, there exists a $v \in N^+(u)$ such that $(v,x) \in E(G)$. Then: \[ N^{++}(u) = \bigcup_{v \in N^+(u)} \text{ext}(u, v) \]
proof: Recall that for any $v \in N^+(u)$, the exterior set is defined as: \[ \text{ext}(u, v) = N^{++}(u) \cap N^+(v) \] Intuitively, the set $\text{ext}(u, v)$ represents the portion of $u$'s second out-neighborhood that is reachable on a path through a specific out-neighbor $v$.

Let $x \in N^{++}(u) / N^+(u)$. By assumption, there exists some $v \in N^+(u)$ such that $x \in N^+(v)$. Then: \[ x \in N^{++}(u) \cap N^+(v) = \text{ext}(u, v) \] So $x \in \bigcup_{v \in N^+(u)} \text{ext}(u, v)$. Thus, \[ N^{++}(u) \subseteq \bigcup_{v \in N^+(u)} \text{ext}(u, v) \] Conversely, suppose $x \in \bigcup_{v \in N^+(u)} \text{ext}(u, v)$. Then there exists $v \in N^+(u)$ such that $x \in \text{ext}(u, v)$, which means: \[ x \in N^{++}(u) \cap N^+(v) \] Hence, $x \in N^{++}(u)$.

So: \[ \bigcup_{v \in N^+(u)} \text{ext}(u, v) \subseteq N^{++}(u) \] Combining both directions, we conclude: \[ N^{++}(u) = \bigcup_{v \in N^+(u)} \text{ext}(u, v) \]
label: Exterior Cover Lemma

content: Given an oriented graph $G=(V,E)$ without back arcs, $G$ can be represented by a Graph Level Order.
proof: We aim to show that $G$ can be systematically partitioned into rooted neighborhoods that satisfy the key properties required by the Graph Level Order structure:

We select a node $v_0 \in G$ of minimum out-degree. This node will serve as the root for defining rooted neighborhoods based on graph distance.

Define rooted neighborhoods $R_i = \{u \in G \mid \text{dist}(v_0,u)=i\}$ for $i=0,1,2,\ldots ,k$. Here, $\text{dist}(v_0,u)$ is the length of the shortest directed path from $v_0$ to $u$. Since $v_0 \in R_0$, each $R_i$ collects all nodes at distance exactly $i$ from $v_0$.

By assumption, $G$ contains no back arcs (arcs going from a node in $R_i$ to a node in $R_j$ with $j < i$). Therefore, the neighborhoods, $R_1,\ldots,R_k$ form a natural total order: \[ R_0 < R_1 < \ldots < R_k \] where $u < v$ if and only if $\text{dist}(v_0, u) < \text{dist}(v_0, v)$. This total order arises because the distance function respects strict inequality between layers, and no arcs "go backward" in terms of distance.

Consider any two distinct nodes $u,v \in R_i $. Since they share the same distance from $v_0$, distance alone cannot order them. To establish a total order within each $R_i$, introduce a secondary ordering metric such as:

Lexicographic order of adjacency lists,
Comparing out-degree values,
Or any consistent tie-breaking scheme on node identifiers.

This ensures any two nodes within the same rooted neighborhood can be compared, completing the total order on the entire vertex set $V$.

Because the graph is oriented and contains no back arcs, arcs only go from nodes in $R_i$ to nodes in $R_{i+1}$ or within the same $R_i$.

Thus, the ordering respects the graph structure, and comparisons are consistent across rooted neighborhoods.

For $u \in R_i $ Interior neighbors are defined for $v \in N^+(u) \subseteq R_{i+1}$ \[ \text{int}(u,v)=N^+(u) \cap N^+(v) \] Exterior neighbors are defined for $v \in N^+(u)$: Nodes reachable from $u$ in two steps but not directly from $u$, and which are reachable from $v$: \[ \text{ext}(u,v)=N^{++}(u)\cap N^+(v) \] Consider an arc $u \to v \in G$, with $v \in R_{i+1}$. This makes $u$ a parent of $v$. Now consider the arc $v \to w \in G$, where $w \in N^+(v)$. There are three possible cases. Either $u \to w \in G$ or $u \to w \notin G, \text{ where } w \in R_i$ or $u \to w \notin G \text{ where } w \in R_{i+1}$.

Case 1: If $u \to w \in G$, then $w \in \text{int}(u, v)$.

Case 2: If $u \to w \notin G$, but $w \in R_{i+1}$, then $w \in \text{ext}(u, v)$.

Case 3: If $u \to w \notin G$ and $w \in R_{i+2}$, then $w \in \text{ext}(u, v)$.

The partition ${R_0,R_1,\ldots,R_k}$ forms a leveled hierarchy of rooted neighborhoods, with a total order on rooted neighborhoods and on nodes within each neighborhood. Interior and exterior neighborhoods are well-defined, preserving the Graph Level Order properties. Hence, under the assumption of no back arcs, $G$ can be represented by a Graph Level Order.

This completes the proof.
label: Graph Level Order Representation of Oriented Graphs without Back Arcs

content: In any oriented graph $G$ represented via a Graph Level Order rooted at a minimum out-degree node, every transitive triangle falls into exactly one of six structural types based on the position of nodes in rooted neighborhoods and the direction of arcs.
proof: We classify all transitive triangles by examining the configuration of the first two arcs and then determine whether a valid third arc can close the triangle transitively.

Row ID	# Exterior	# Back	# Interior/	Triangle Possible?
1	0	0	3	Yes
2	0	1	2	No
3	0	2	1	Yes
4	1	0	2	Yes
5	1	1	1	Yes
6	1	2	0	Yes
7	2	0	1	Yes
8	2	1	0	No

\caption{\textit{Enumeration of possible combinations of arc types forming transitive triangles.}} We now describe the realizable cases:

Case 1(Interior Triangle): All three nodes lie in the same rooted neighborhood $R_i$. Arcs: $x \to y, x \to z, y \to z \in G$. All arcs are interior.
Case 2 (Invalid): One back arc and two interior arcs. If both $y$ and $z$ lie in $R_i$ and one arc points backward, transitivity cannot hold unless $x$ is in $R_i$, which contradicts the rooted structure. Hence, this is not possible.
Case 3 (Back Arc Triangle I): Two back arcs and one interior arc. Here, both $x, y \in R_i$, and $z \in R_{i+1}$. All arcs are: $x \to y, z \to x, z \to y$. This forms a valid triangle.
Case 4 (Interior-Exterior Triangle): One interior arc and two exterior arcs. A common parent $x \in R_i$ maps to children $y, z \in R_{i+1}$ with $ x \to y, x \to z, y \to z \in G $. Standard configuration for load balancing, defining the interior nodes.
Case 5 (Back Arc Triangle II): One arc is a back arc $z \to y$, one interior$x \to y$, and one exterior$x \to z$.
Case 6 (Back Arc Triangle III): One exterior arc and two back arcs connecting three different rooted neighborhoods $R_i$, $R_{i+1}$ and $R_{i+2}$, e.g., $x \to y, z \to x, z \to y$, where $x \in R_i$ $y \in R_{i+1}$ and $z \in R_{i+2}$ forms a valid triangle.
Case 7 (Exterior Arcs Case 2:): Two exterior arcs and one interior arc, e.g., $ x \to z, y \to z, x \to y $, where $x, y \in R_i$, $z \in R_{i+1}$.
Case 8 (Invalid): One back arc and two exterior arcs. The assumption of two exterior arcs implies $x \to y, x \to z)$, where $x \in R_i$ and $y, z \in R_{i+1}$. This third arc cannot be $y \to x$ or $z \to y$ since $G$ is an oriented graph. The other option that would make this a transitive triangle would be the arcs $y \to z$ or $z \to y$, neither of which are back arcs since $y$ and $z$ are in the same rooted neighborhood.

Since all structurally valid triangles fall into one of these categories, and we have excluded all others through case exhaustion, the theorem follows.
label: Classification of Transitive Triangles in the Graph Level Order

content: In any oriented graph, without back arcs, the minimum out-degree node $ v_0 $ within a Graph Level Order structure provides a well-ordering, enabling an inductive analysis of all other nodes in the graph.
proof: First, remember that we are under the assumption that we do not have back arcs.
We have already shown that under this assumption, the rooted neighborhoods in a Graph Level Order form a total order. Further, they are a discrete total order.
By definition, a set is considered well-ordered if every non-empty subset of that set has a least element.
A discrete total order is a total order, where each element has a distinct next element in the order.
Since a discrete total order has a clear distinction between elements, any non-empty subset will always have a smallest element according to the order.
This fulfills the condition of being well-ordered.
Every non-empty subset will have a least element, which is the defining characteristic of a well-ordered set.
Thus, the total order defined by the distance from $v_0$ on the set of rooted neighborhoods $R_1, R_2, \ldots$ constitutes a well ordering.
label: Graph Level Order Supports Induction

content: In a Graph Level Order containing a Seymour diamond, the ambiguity introduced by dual paths is resolved via exterior neighbors.
proof: Recall that a Seymour diamond is a four-vertex oriented graph $G$, with vertex set $V = \{x, y, w, u\}$ and the following directed edges: \[ x \to y,\quad x \to w,\quad y \to u,\quad w \to u. \] Note that the edge $x \to u$ is not present in the graph.

Let us also recall the definition of an exterior neighbor. For a parent node $x$, and a child $y \in N^+(x)$, we define the set of exterior neighbors through $y$ as: \[ \text{ext}(x, y) = N^{++}(x) \cap N^+(y). \] Since $x \to y$ and $y \to u$, and there is no direct edge $x \to u$, it follows that $u \in N^{++}(x)$. Moreover, because $u$ is a direct out-neighbor of both $y$ and $w$, we have $u \in N^+(y)$ and $u \in N^+(w)$. Thus, $u \in \text{ext}(x, y)$ and $u \in \text{ext}(x, w)$, meaning $u$ is an exterior neighbor of $x$ through both child vertices.

Now consider the rooted neighborhood structure of the graph $G$. Suppose $x$ lies in level $R_i$. Since both $y$ and $w$ are direct out-neighbors of $x$, they belong to level $R_{i+1}$. Continuing the level-wise expansion, since $u$ is a direct out-neighbor of both $y$ and $w$, it lies in level $R_{i+2}$.

Without applying Graph Level Order, the paths $x \to y \to u$ and $x \to w \to u$ would cause $u$ to be counted twice\textendash once along each path. However, the definition of exterior neighbors accounts for this redundancy. Since $u$ is reachable via two length-2 paths from $x$, but appears only once in the exterior neighbor set, we preserve the correct multiplicity: \[ |\text{ext}(x, y)| = |\text{ext}(x, w)| = 1. \] Hence, the Graph Level Order, via the concept of exterior neighbors, properly resolves the ambiguity introduced by the dual paths in a Seymour diamond.
label: Exterior Neighbors Resolve Seymour Diamonds

content: Suppose a node in an oriented graph $G$ does not have the Decreasing Neighborhood Sequence Property. Then this node will have its out-degree at least double in $G^2$.
proof:
label: Decreasing Neighborhood Sequence Property Lemma

content: Let $G$ be an oriented graph, and let $v_0$ be a node of minimum out-degree in $G$. If nodes at distance $i$ must have degree at least $i)$, then for every rooted neighborhood $R_i$ at distance $i$, there exists at least one node whose second interior out-degree is at least as large as its first interior out-degree: \[ |N^{++}_{\text{int}}(v)| \geq |N^+_{\text{int}}(v)|. \]
proof: We will provide a constructive algorithm and use properties of permutation groups to show that the condition holds. That is, we will show that we can always map each node in $R_i$ to $i$ disjoint cycles. The proof relies on the fact that the internal structure of $R_i$ is already known to be a permutation into disjoint cycles of length $\geq 3$. This inherent structure ensures that within $R_i$, each node has exactly one outgoing and one incoming edge. For a node $v \in R_i$, its first interior out-degree, denoted $|N^+_{\text{int}}(v)|$, refers to the number of nodes $v \to u$ such that $u \in R_i$. Similarly, the second interior out-degree of $v$, denoted $|N^{++}_{\text{int}}(v)|$, refers to the number of nodes $w \in R_i$ such that there exists a node $u \in R_i$ with edges $v \to u \to w$. We begin this proof with a statement of a simple algorithm and will show that this algorithm is feasible for the Interior Degree Doubling. The purpose of this algorithm is to give an example as a generalization of a load balancing algorithm, and show this is possible. This is not the only such algorithm. Indeed, the number of derangements $D_n$ grows at a complexity of $\frac{n!}{e}$. That fraction includes transpositions, or 2-cycles which are outlawed. Removing the number of 2-cycles from this growth rate does not reduce this by much. We outlaw 2-cycles because they are not allowed in oriented graphs and we would like this permutation to transpose back to our graph theoretical framework. To that nature, we have already proved in Section 4 (Initial Lemmas) that all our counter-examples must have minimum out-degree at least 3. This agrees with the minimum degree requirements for a cycle.

A list of nodes $R_i$, integer distance $i$
Each node in $R_i$ is assigned exactly $i$ interior neighbors
Initialize a dictionary $assigned\_neighbors$ mapping each node to an empty set
Let $n \gets |R_i|$
- State $assigned \gets 0$
- For{$step = 1$ to $n - 1$}
- State $v \gets R_i[(\text{index}(u) + step) \bmod n]$
- If{$v \neq u \And v \notin assigned\_neighbors[u]$}
- State Add $v$ to $assigned\_neighbors[u]$
- State $assigned \gets assigned + 1$
- EndIf
- If{$assigned = i$}
- State \textbf{break}
- EndIf
- EndFor
EndFor

\Return $assigned\_neighbors$ \caption{Given a rooted neighborhood $R_i$, this algorithm assigns each node to participate in exactly $i$ interior cycles, simulating repeated interior degree mappings for each level. This construction ensures every node maps to interior neighbors via multiple cycle layers, supporting the interior degree doubling condition.} \textbf{Example:} Consider the neighborhood $R_i=Z_6=\{1,2,3,4,5,6\}$. One possibility for the algorithm is to return the following two disjoint permutations: \\ (1 2 3 4 5 6) and (1 3 5)(2 4 6) Because each node appears once in each cycle representation, these two permutations correspond to two independent mappings. Continuing, since each node has a first neighbor in each cycle, this yields: \[ |N_{int}^+(v)|=2,|N_{int}^{++}(v)|=2. \] This makes every node in $R_i$ a degree doubling node. Even with limitations on 2-cycles, such a mapping algorithm will allow for the utilization of combinatorial space in $R_i$. We can actually look at this as we begin in the rooted neighborhood $R_i$. \begin{itemize} \item There are $i$ choices for the starting node. \item There are $i - 1$ choices for the second node (we must exclude the first node). \item There are $i - 2$ choices for the third node (we must exclude the first two nodes. \item $\ldots$ \item There is one choice for the last node (we must exclude all other nodes). \end{itemize} This results in $i!$ possible candidate paths (modulo orientation constraints). This number of such derangements still grows factorially at roughly $\frac{n!}{e}$. This indicates that we still have an abundance of cycle permutations with the 2-cycle restrictions. The structure of these rooted neighborhoods forms a permutation on the set $R_i$, which decomposes into disjoint cycles. Since oriented graphs prohibit 2-cycles, each of these cycles must have a length $k \geq 3$. A key result from group theory (Lagrange's Theorem) tells us that the order of any subgroup divides the order of the full symmetric group on $R_i$, $S_{|R_i|}$. These permutations decompose into disjoint cycles whose lengths divide $|R_i|$, and the cycles are structure-preserving under composition. Because Lagrange's theorem partitions $R_i$, into subsets that divide $|R_i|$, we know that any remaining permutations will always divide the order of the group and no nodes will ever be left without a cycle. Thus, each node is mapped to a unique successor in its cycle. Therefore, in every cycle of length $k \geq 3$, each node has out-degree 1 and maps to another node in the same cycle, producing a single out-edge within $R_i$. The node it maps to will also have a unique out-neighbor since cycles do not repeat nodes. This yields a second-level interior neighbor. Consider any node $v$ within one of these cycles of length $k \geq 3$. By definition of a cycle within $R_i$, $v$ has exactly one outgoing edge $v \to u$ where $u \in R_i$. Therefore, $|N^+_{int}(v)|=1$. Furthermore, since $k \geq 3$, $u$ must also have exactly one outgoing edge $u \to w$ where $w \in R_i$ and $w \neq v$. Thus, $w$ is a unique second-level interior neighbor, implying $|N^{++}_{int}(v)|=1$. Since for every node $v$ in any such rooted neighborhood $R_i$, we have \[ |N^+_{\text{int}}(v)|=1 \] and \[ |N^{++}_{\text{int}}(v)|=1, \] the condition \[ |N^{++}_{\text{int}}(v)| \geq |N^+_{\text{int}}(v)| \] is satisfied.\\ Since such cycle decompositions always exist under the algorithm and orientation constraints, there must be at least one node in every $R_i$ that satisfies the interior degree doubling condition. This result is also aligned with Lemma \ref{lowdeg} (Minimum Out-Degree $< 3$) and related results from \cite{KL}, confirming that low out-degree nodes within cycles tend to satisfy the degree doubling property.
label: Interior Degrees Double

content: Let $G$ be an oriented graph represented by a Graph Level Order with root node $v_0$. Further , assume $G$ has no back arcs. Suppose $u_i \in R_i$ has its interior out-degree double and $\text{ext}(u_{i-1}, u_i) = R_{i+1}$ . Then if $|R_{i+1}| \geq |R_{i+2}|$, $u_i$ will have its exterior out-degree double as well, causing the overall out-degree of $u_i$ to double.
proof: Let us begin by restating our definitions. For a node $u_i$, we define the interior out-degree with respect to a parent $u_{i-1}$ as \[ |\text{int}(u_{i-1}, u_i)|. \] Similarly, we define the exterior out-degree with respect to that same parent as \[ |\text{ext}(u_{i-1}, u_i)|. \] By the assumption that $u_i$'s interior out-degree doubles, we are assuming that the number of second interior neighbors of $u_i$ with respect to $u_{i-1}$ is at least as large as its number of first interior neighbors. That is, \[ |N^{++}_{\text{int}}(u_i)| \geq |N^+_{\text{int}}(u_i)|. \] By Lemma (Partition of Node's Degree), and the lack of back arcs in $G$, the behavior of a node's degree doubling is dependent on its interior out-degree doubling and its exterior out-degree doubling. Because these sets are disjoint, they act independently of one another. Thus, if we can also show that $u_i$'s exterior out-degree doubles, it will show that $u_i$'s overall degree doubles.

By assumption, the nodes of $\text{ext}(u_{i-1}, u_i)$ are in $R_{i+1}$. These are the first exterior out-neighbors of $u_i$. The nodes in $R_{i+2}$ are the first out-neighbors of the nodes in $R_{i+1}$, thus they are the second exterior out-neighbors of $u_i$. The assumption that $|R_{i+1}| = |R_{i+2}|$ says that the node $u_i$ has an equal number of first exterior out-neighbors and second exterior out-neighbors. That is, \[ |N^{++}_{\text{ext}}(u_i)| = |N^+_{\text{ext}}(u_i)|. \] This makes $u_i$ satisfy the degree doubling condition for its exterior degree. We have already shown that $u_i$ satisfies the degree doubling condition for its interior degree, so $u_i$ satisfies the degree doubling condition for its overall degree.

This completes the proof.
label: Exterior Degree Doubling

content: Suppose that $G$ is an oriented graph represented by a Graph Level Order, where there are no back arcs, with $u_i \in R_i$ and \[ v_{i+1} \in N^+(u_i) \cap R_{i+1}, \] where both $u_i$ and $v_{i+1}$ have the Decreasing Neighborhood Sequence Property (DNSP) and the node $v_{i+1}$ has its interior degree double. Then, for all \[z \in \text{ext}(u_i, v_{i+1}),\] we have \[ |\text{ext}(v_{i+1}, z)| < |\text{ext}(u_i, v_{i+1})|. \] That is, the exterior degree of $v_{i+1}$ with respect to $u_i$ decreases for every second neighbor $z$ of $u_i$.
proof: Let us first restate our definitions. The DNSP say that a node's second neighborhood is strictly less than its first neighborhood \[ |N^{++}(u)| < |N^+(u)|. \] Recall that for an arc $u_i \to v_{i+1}$, \[ \text{int}(u_i, v_{i+1}) = N^+(x) \cap N^+(v_{i+1}).\] Similarly, for that same arc $u_i \to v_{i+1}$, \[ \text{ext}(u_i, v_{i+1}) = N^{++}(u_i) \cap N^+(v_{i+1}).\] And for the arc $v_{i+1} \to z$, \[ \text{ext}(v_{i+1}, z) = N^{++}(v_{i+1}) \cap N^+(z). \] Assume that we have a node $v_{i+1} \in R_{i+1}$, whose interior degree doubles. We assumed there are no back arcs, which means that for all \[ \forall w \in \text{ext}(u_i, v_{i+1}) \cap \text{ext}(v_{i+1}, z) = \emptyset. \] For the sake of contradiction, suppose that there exists a $z \in \text{ext}(u_i, v_{i+1})$ such that \[|\text{ext}(v_{i+1}, z)| \geq |\text{ext}(u_i, v_{i+1})|.\] We can break the degree of $v_{i+1}$ down into two components (remember there are no back arcs that would be a third component), its interior degree and its exterior degree \[ d^+(v_{i+1}) = |\text{int}(u_i,v_{i+1})|+|\text{ext}(u_i,v_{i+1})|. \] By assumption, the node $v_{i+1}$ has its interior degree double. Thus, we have that if we can show that $v_{i+1}$'s exterior degree also doubles, it would lead to a contradiction because $v_{i+1}$ would have both its interior and exterior degree doubling, and thus its overall degree doubling, violating the DNSP.

Our assumption for the sake of contradiction was that $z \in \text{ext}(u_i, v_{i+1})$ such that \[ |\text{ext}(v_{i+1}, z)| \geq |\text{ext}(u_i, v_{i+1})|. \] The node $v_{i+1}$'s out-degree will be impacted by $\text{ext}(u_i, v_{i+1})$ and $\text{ext}(v_{i+1}, z)$. This means that \[ z \in \text{ext}(u_i, v_{i+1}) = N^{++}(x) \cap N^+(v_{i+1}) = R_{i+2} \] \begin{equation} \begin{split} |\text{ext}(v_{i+1}, z)| &\geq |\text{ext}(u_i, v_{i+1})| \\ |\text{ext}(v_{i+1}, z)| + |\text{ext}(u_i, v_{i+1})| &\geq |\text{ext}(u_i, v_{i+1})| + |\text{ext}(u_i, v_{i+1})|\\ |\text{ext}(v_{i+1}, z)| + |\text{ext}(u_i, v_{i+1})| &\geq 2 \cdot|\text{ext}(u_i, v_{i+1})| \end{split} \end{equation} Thus we have the following conditional:

If \[ |\text{ext}(v_{i+1}, z)| \geq |\text{ext}(u_i, v_{i+1})|, \] then \[ |\text{ext}(v_{i+1}, z)| + |\text{ext}(u_i, v_{i+1})| \geq 2 \cdot |\text{ext}(u_i, v_{i+1})|\] We have two exterior sets on the left of the equation that we would like to sum, but we need to be sure that there is no node \[ w \in \text{ext}(v_{i+1}, z) \cap \text{ext}(u_i, v_{i+1}). \] Because this is a sum of set sizes, to correctly compare the sizes of these exterior sets, we first need to ensure that they are disjoint. We will define a set to represent their intersection and denote it $I$. Consider the set \[ I = N^{++}(v_{i+1}) \cap N^+(z) \cap N^{++}(u_i) \cap N^+(v_{i+1}). \] The set \[ I(x, v_{i+1}, z) = \text{ext}(v_{i+1}, z) \cap \text{ext}(u_i, v_{i+1}) \] is the intersection of those two sets.

Our job is to determine the cardinality of \[ I(u_i, v_{i+1}, z). \] Namely can there exist a \[ w \in I(u_i, v_{i+1}, z). \] $w \in I$ implies that there are two possibilities for $w$. Either \[ w \in N^{++}(u_i) \cap N^+(v_{i+1}) \] or \[ w \in N^{++}(v_{i+1}) \cap N^+(z).\] If \[ w \in N^{++}(u_i) \cap N^+(v_{i+1}), \] This would mean that there was an arc $u_i \to w$ across two rooted neighborhoods, skipping all nodes in the rooted neighborhood $R_{i+1}$. We do not allow that through our shortest path constructions though.

If \[ w \in N^{++}(v_{i+1}) \cap N^+(z), \] then we have an arc from the rooted neighborhood $R_{i+2}$ where $z$ lies, to $R_{i+1}$ where $v_{i+1}$ and $w$ would be. This arc $z \to w$ would represent a back arc though, which we assumed did not exist in this graph. This would mean that the exterior degree of $v_{i+1}$ is at least as large as the exterior degree of $u_i$.

From $|\text{int}(u_i, v_{i+1})|$ doubling, $v_{i+1}$'s influence in $G[N^+(x)]$ grows, yet its exterior degree should decrease due to the DNSP. The absence of back arcs prevents any increase in $v_{i+1}$'s exterior degree from its second neighbors.

Thus, the assumption \[ |\text{ext}(v_{i+1},z)| \geq |\text{ext}(u_i,v_{i+1})| \] leads to a contradiction, confirming that \[ |\text{ext}(v_{i+1},z)| < |\text{ext}(u_i,v_{i+1})| \] for all \[z \in \text{ext}(u_i,v_{i+1}).\] Therefore, the lemma holds: for all $z \in \text{ext}(u_i,v_{i+1})$, the exterior degree of $v_{i+1}, z$ is strictly smaller than the exterior degree of $u_i, v_{i+1}$. In other words, the size of the exterior neighbors decreases between consecutive neighborhoods.
label: Decreasing Exteriors Lemma

content: Suppose $G$ is an oriented graph with a node $v_0$ of minimum out-degree, and define rooted neighborhoods $R_0, R_1, \ldots, R_k$ based on distance from, constructed without back arcs. Assume $G$ is a minimal counterexample to the Second Neighborhood Conjecture (SSNC), i.e., every node $x \in G$ satisfies the Decreasing Neighborhood Sequence Property (DNSP): $|N^{++}(x)|<|N^+(x)|$. Then, for any node $u_i \in R_i$ with $i \geq 1$, and any parent $u_{i-1} \in R_{i-1}$ of $u_i$, the number of common out-neighbors satisfies $|N^+(u_{i-1}) \cap N^+(u_i)| \geq i$.
proof: Let us first restate our definitions. The DNSP says that a node's second neighborhood is strictly less than its first neighborhood $|N^{++}(u)| < |N^+(u)|$. For an arc $u \to v$ with $u \in R_{i-1}$ and $v \in R_i$, define: The interior out-degree of $v$ with respect to $u$ as \[|\text{int}(u,v)|=|N^+(u) \cap N^+(v)|.\] The exterior out-degree of $v$ with respect to $u$ as \[|\text{ext}(u,v)|=|N^{++}(u) \cap N^+(v)|.\] The interior neighbors will lie in the rooted neighborhoods $R_i$.

For any $v$, we are still undergoing the practice of splitting its total out-degree into its interior degree and its exterior degree. That is, its degree equation can be stated as $d^+(v)=|\text{int}(u,v)|+|\text{ext}(u,v)|$. We proceed by induction on distance $i$ from $v_0$:

Base case (i=1): Let $u_1 \in R_1$ with parent $v_0 \in R_0$. This is exactly what we saw in Lemma (Interior Load Balancing), with $|N^+(v_0) \cap N^+(u_1)| \geq 1$ ,so the base case holds.

Induction hypothesis: Assume for all $1 \leq k \leq i$, and any $u_k \in R_k$ with parent $u_{k-1} \in R_{k-1}. $ \[ |N^+(u_{k-1}) \cap N^+(u_k) | \geq k \] Inductive step: Consider any $u_{i+1} \in R_{i+1}$ with parent $u_i \in R_i$. Suppose, for contradiction, \[ |N^+(u_i) \cap N^+(u_{i+1})| < i+1 \] i.e., \[ |\text{int}(u_i, u_{i+1})| \leq i \] The minimum out-degree node $v_0$ says that the node $u_{i+1}$ must have an out-degree of at least $\delta$. Since $u_{i+1}$ has out-degree at least $\delta$, we have that \[ |\text{ext}(u_i, u_{i+1})| = d^+(u_{i+1}) - |\text{int}(u_i, u_{i+1})| \geq \delta - i. \] Because we have the Induction Hypothesis in previous neighborhoods, we can use Lemma (Interior Degrees Double). As such, we can invoke Lemma (Decreasing Exteriors), which states that because we have interior degree of at least $k$ for every node $u_k \in R_k$ along the path from $v_0$ to $u_i$ (the parent node of $u_{i+1}$), exterior degrees must strictly decrease as we traverse outwards. Formally, for nodes $u_k \in R_k$ and $u_{k+1} \in R_{k+1}$, we have the following equation: \[ |\text{ext}(u_k,u_{k+1})| > |\text{ext}(u_{k+1},z)| \] for any $z \in \text{ext}(u_k,u_{k+1})$. This implies exterior degrees along the path decrease from $\delta$ down by at least 1 at each step, bounding \[ |\text{ext}(u_i,u_{i+1})|<\delta -i. \] But this contradicts the earlier inequality that \[ |\text{ext}(u_i,u_{i+1})| \geq \delta - i. \] This contradiction arises from assuming the interior degree is less than $i$+1. Hence, the assumption is false, and we conclude: \[ |N^+(u_i)\cap N^+(u_{i+1})| \geq i+1 \] This completes the induction and proves the lemma.
label: Generalized Load Balance Lemma

content:

algorithmic
\State Determine a minimum out-degree node $v_0 \in V$.
\State Partition the set of vertices $V$ into ordered sets $R_0, R_1, \ldots, R_k$ based on their out-distance from $v_0$, where $R_0 = \{v_0\}$ and $R_i = N^+(R_{i-1}) \setminus \bigcup_{j=0}^{i-1} R_j$ for $i > 0$.
\For{$i = 0$ to $k$}
- \For{each node $u_i \in R_i$}
  - \If{there exists an arc $(u_i, w) \in E$ such that $w \in R_k$ where $k < i$}
    - \State $u_i \rightarrow \text{degree\_doub[back]}$
    - \State HALT
  - \Else
    - \If{$i > 0$}
      - \If{$|\text{int}(u_{i-1}, u_i)| < i$}
      - \State $u_{i-1} \rightarrow \text{degree\_doub[dense]}$
      - \State HALT
      \EndIf
    \EndIf
  \EndIf
\EndFor
\If{$|R_i| \leq 2$}
- \If{$i > 0$}
  - \State $u_{i-1} \rightarrow \text{degree\_doub[size]}$
  - \State HALT
  \EndIf
\EndIf

\EndFor
proof:
label: Algorithm for Finding Degree Doubling Nodes

content: Let $ G $ be an oriented graph rooted at a minimum out-degree node $ v_0 $, with rooted neighborhoods $ R_0, R_1, \dots, R_k $ constructed by layering (i.e., $ R_i $ is the set of nodes at distance $ i $ from $ v_0 $). Suppose all nodes satisfy the Decreasing Neighborhood Sequence Property (DNSP), and that the graph contains no back arcs. Then for all $ i \geq 0 $, \[ |\{ y \in \text{ext}(u, v) \text{ s.t. } u \in R_i,\ v \in R_{i+1},\ y \in R_{i+2} \}| \leq d^+(v_0) - i. \]
proof: We proceed by induction on the distance $ i $.

\textbf{Base Case ($ i = 0 $):} The neighborhood $ R_0 = \{v_0\} $, and its out-neighbors form $ R_1 $, with $ |R_1| = d^+(v_0) $ by definition. Now consider $ R_2 $, which consists of nodes reachable by an arc from nodes in $ R_1 $. We assume that all nodes, including $v_0$ and all nodes in $R_1$ have the DNSP. Let $ v_0 \in R_0 $, $ v \in N^+(v_0) = R_1 $, and define $ \text{ext}(v_0, v) := N^{++}(v_0) \cap N^+(v) $. From DNSP holding for $v_0$, we have \[ |N^{++}(v_0)| < |N^+(v_0)| = d^+(v_0), \] So no matter what set we intersect $N^{++}(v_0)$ with from $R_1$, the resulting intersection $N^{++}(v_0) \cap N^+(v)$ will have a smaller cardinality than $d^+(v_0$.

This is the bound we need for the exterior set of $v_0 \to v$. \[ |\text{ext}(v_0, v)| \leq d^+(v_0) - 1. \] \textbf{Inductive Hypothesis:} Assume that for some $ i \geq 0 $, \[ |\{ y \in \text{ext}(u, v) \text{ s.t. } u \in R_i,\ v \in R_{i+1},\ y \in R_{i+2} \}| \leq d^+(v_0) - i. \] \textbf{Inductive Step:} Consider $ u \in R_{i+1} $, and $ u \to v \in G $, where $v \in R_{i+2}$, and we will examine $ \text{ext}(u, v) = N^{++}(u) \cap N^+(v) $. From Lemma \ref{del} (Decreasing Exteriors Lemma), we have: \[ |\text{ext}(u, v)| < |\text{ext}(w, u)|, \] for any parent $ w \in R_i $, $ u \in R_{i+1} $.

By the inductive hypothesis, \[ |\text{ext}(w, u)| \leq d^+(v_0) - i. \] We can combine these inequalities to get, \[ |\text{ext}(u, v)| < d^+(v_0) - i \Rightarrow |\text{ext}(u, v)| \leq d^+(v_0) - (i + 1). \] Hence, the bound holds for level $ i + 1 $. This completes the induction and proves the lemma.
label: DNSP Impact on Rooted Neighborhood Size

content: Let $G$ be an oriented graph with minimum out-degree node $v_0$, where the out-degree of $v_0$ is $\delta$. Suppose all nodes in $G$ satisfy the DNSP. Then the rooted neighborhoods $R_i$ satisfy the bounds: \[|R_0| = 1,\] \[|R_1| = \delta,\] \[|R_i| \leq \delta - (i - 1)\]
proof: We proceed by induction on the distance $i$ of rooted neighborhoods $R_i$. \textbf{Base cases:} \begin{itemize} \item $R_0 = \{v_0\}$, so $|R_0| = 1$ by definition. \item $R_1 = N^+(v_0)$, so $|R_1| = \delta$, again by definition. \end{itemize} The DNSP says $|N^+(v_0)| > |N^{++}(v_0)|$. All of the out-neighbors of $v_0$ are in the rooted neighborhood $R_1$ and every second neighbor of $v_0$ will be in the rooted neighborhood $R_2$. By Lemma (Interior Load Balancing), these children $u \in R_1$ help prevent $v_0$ from becoming a degree doubling node by forming cycle(s) in $R_1$. This bounds the number of external neighbors in $R_2$ and thus the size of $|R_2|$. \textbf{Inductive hypothesis:} Assume that for some $k < i$, we have: \[ |R_k| \leq \delta - (k - 1)%, \text{and for all } u \in R_k, \text{ext}(u) < \delta - (k - 1), \quad \text{int}(u) > k - 1. \] \textbf{Inductive step:} We consider the neighborhood $R_{k+1}$. We apply Lemma (DNSP Impact on Neighborhood Size), which implies: \[ |R_{k+1}| < |R_k| \leq \delta - (k-1) \Rightarrow |R_{k+1}| \leq \delta - ((k+1)) - 1)=\delta - k.

We conclude that the inductive structure holds for all $i$, giving: \[ |R_i| \leq \delta - (i - 1), \]
label: Formula for Rooted Neighborhood Size

content: Let $G$ be an oriented graph with minimum out-degree $v_0$ and node rooted neighborhoods $R_i$ and $R_j$, with $i > j$. If there are no back arcs from any node in $R_i$ to any node in $R_j$, then $R_i$ and $R_j$ are disjoint (i.e., $R_i \cap R_j = \emptyset$).
proof: Assume, for the sake of contradiction, that $R_i$ and $R_j$ are not disjoint. Then there exists a node $v$ such that $v \in R_i \cap R_j$. This means that $v$ is in both $R_i$ and $R_j$. By the definition of $R_i$, this means that $v$ is at distance $i$ from $v_0$. Likewise, by the definition of $R_j$, this means that $v$ is at distance $j$ from $v_0$. We assumed that $i \neq j$, so we are saying that a node $v$ is at two different distances from $v_0$. This is a contradiction, as a node cannot simultaneously be at distance $i$ and $j$ from $v_0$ when $i \neq j$, because there is a unique distance from $v_0$ to any node. Therefore, $R_i$ and $R_j$ must be disjoint. In other words, when there are no back arcs, then different rooted neighborhoods are disjoint.
label: Back Arcs Necessary

content: Let $G$ be an oriented graph with minimum degree node $v_0$ and rooted neighborhoods $R_i$ and $R_j$, where $j < i$. If $R_i$ and $R_j$ are not disjoint, then there exists a back arc from a node in $R_i$ to a node in $R_j$.
proof: Suppose that $R_i$ and $R_j$ are not disjoint. Then there exists a node $v$ such that $v \in R_i \cap R_j$. This means that $v \in R_i$ and $v \in R_j$. Since $i < j$, and both $v \in R_i$ and $v \in R_j$, there must be a path from $v_0$ to $v$ of length $i$ and a path from $v_0$ to $v$ of length $j$. The only way this is possible is if there is a back arc from a node in $R_i$ to a node in $R_j$. Then we would extend the path from $v_0 \to R_i \to v_1 \to back\_arc \to R_j \to v_2 $. Thus, the existence of non-disjoint rooted neighborhoods, when $i
If there were no back arc from \(R_i$ to $R_j$, then any path from $v_0$ to a node in $R_i$ would have length $i$, and any path to a node in $R_j$ would have length $j$. If a single node $v$ were in both $R_i$ and $R_j$, it would imply two different shortest path lengths from $v_0$ to $v$, which is impossible in a simple directed graph.
label: Back Arcs Sufficient

content: Let $G$ be an oriented graph with rooted neighborhoods $R_i$ that are well-ordered by their indices. If a node $u_i \in R_i$ whose interior degree doubles neighborhood in $R_i$, and it has its first back arc to a node $v_k$ in neighborhood $R_k$, where $k < i$, meaning there is no back arc from $u_i$ to $R_j$ where $k < j < i$, then the size of the second out-neighbors $N^{++}(u_i)$ is at least $\text{deg}(v_k)$, and this will cause the total degree of $u_i$ to double as well.
proof: We assume here that all nodes in $G$ have the DNSP. Assume that $u_i \in R_i$ has its earliest back arc to $v_k \in R_k$ where $k < i$. A back arc $u_i \to v_k$ means $v_k$ is a first out-neighbor of $u_i$. The neighbors of $v_k$ are then at distance two from $u_i$ through $v_k$ (a path of length two: $u_i \to v_k \to N^+(v_k)$).

By 'first back arc,' we mean the back arc originating from $u_i$ that targets the rooted neighborhood with the largest index $k$ such that $k < i$ and there are no back arcs from $u_i$ to any $R_j$ where $k < j < i$.

We also have that by the interior degree doubling of $u_i$ and the lack of back arcs before $i$, we know that $u_i$ will have only interior and exterior arcs. By $u_i$ having its interior degree double, if we can show that its exterior degree will double, then its overall degree will double. We just showed that $w \in N^+(v_k)$ was a second out-neighbor of $u_i$ through an exterior arc. By Lemma (DNSP Impact on Neighborhood Size), we have that $\text{ext}(u_{i-1}, u_i) < \delta - i$, for some parent $u_{i-1} \in R_{i-1}$ of $u_i$. Similarly, because $v_0$ is a minimum out-degree node in $G$ we have that $d^+(v_k) = |N^+(v_k)| \geq \delta$. We can combine these two inequalities and we see that \[ |N^+(v_k)| \geq \delta > \delta - i > \text{ext}(u_{i-1}, u_i). \] Simplifying, we see that \[ |N^+(v_k)| > \text{ext}(u_{i-1}, u_i). \] Even the situation where $v_k \in R_{i-1}$ would not stop $u_i$ from becoming a degree-doubling node because Lemma (Generalized Load Balance) states that $i$ of $u_i$'s neighbors must be interior neighbors. This causes the inequality to hold.

We need to consider the scenario that $u_i$ sends more back arcs to other nodes later than $v_k$. In this situation, we would have a similar calculation where the number of neighbors of this new back arc would be greater than the number of exterior arcs. Indeed, the inequities are even greater because these back arcs would bring in new nodes, and the exterior arcs stay the same for each back arc.

This causes the total degree of $u_i$ to double because $u_i$ has more second out-neighbors.
Therefore, the back arc from $u_i$ to $v_k$ causes the second out-neighbors of $u_i$ to increase to at least $d^+(v_k)$, which is greater than the number of first out-neighbors of $u_i$, causing its degree to double.
label: No Back Arcs

content: Let $ G $ be an oriented graph where all nodes satisfy the Decreasing Neighborhood Sequence Property (DNSP). Let $v_0$ be a minimum out-degree node used to set up our rooted neighborhood partition. Then Seymour's conjecture holds true for $G$.
proof: By Lemma (DNSP Neighborhood Size Property), the sizes of rooted neighborhoods $|R_1|, |R_2|, \ldots$ form a strictly decreasing sequence of positive integers. Consequently, there exists a smallest $i > 0$ such that \[ |R_i| \leq 2. \] Let $u_{i-1} \in R_{i-1}$ be a parent of the nodes in $R_i$.

Case 1: If $|R_i| = 1$, say $R_i = \{v\}$.

Then $u_{i-1}$ has an exterior out-neighbor $v$. Since $|R_i|$ is minimal, $|R_{i-1}| > 1$. By Lemma (General Load Balancing), $v$ should have an interior degree of at least $i$. However, with only one node in $R_i$, this is impossible without violating the DNSP at some previous node, which leads to degree doubling.

Case 2: If $|R_i| = 2$, say $R_i = \{v_1, v_2\}$.

Then the parent $u_{i-1}$ had at least two exterior neighbors. For $v_1$ and $v_2$ to maintain the load balancing, they would need interior connections. However, with only two nodes, at least one node must have all its outgoing arcs to $R_{i+1}$ or back to earlier neighborhoods, forcing a degree-doubling scenario for its predecessor in $u_{i-1}$.
label: Degree Doubling by Exterior Decreasing

content: In an oriented graph $G$ with a minimum out-degree node $v_0$ and rooted neighborhoods $R_1, R_2, \ldots R_n$, the shrinkage of neighborhoods and growth of interior degrees guarantees an inevitable collision.

Two scenarios emerge:

Case 1: The rooted neighborhoods shrink rapidly while interior degrees grow. Eventually, no oriented graph can support the required structure, forcing degree doubling.
Case 2: For very small minimum degree $\delta$, the neighborhoods shrink slowly and interior degree growth does not immediately force a collision before nodes run out.

proof:
label: Degree-Doubling by Rooted Neighborhood Density

content: Let $ G $ be an oriented graph with minimum degree $ k $. Then there will be a rooted neighborhood that reaches maximal density.
proof: We begin by stating Lemma (Generalized Load Balance). This states that as we move further from the minimum out-degree node, $v_0$, the nodes are forced to take on more of the load.

In particular, we see that in the rooted neighborhood $R_i$, each node must have an interior out-degree of at least $i$ in order to keep all of its predecessors in the chain of rooted neighborhoods from $v_0$ from having their degrees double.

Thus, we have a series of rooted neighborhoods that are getting smaller as we get further from the minimum out-degree node. At the same time, these rooted neighborhoods are expected to hold fewer nodes of higher degree, i.e., a graph of more arcs. This is progressively leading to more densely rooted neighborhoods. As described in Corollary (Degree-Doubling by Rooted Neighborhood Density), this cannot continue forever. There must be a last, most dense, rooted neighborhood.
label: Occurrence of Last Dense Rooted Neighborhood

content: Let $ G $ be an oriented graph with minimum degree $ \delta $, and let the most dense graph be in the rooted neighborhood $ R_i $. Then every node in the rooted neighborhood $ R_i $ has its degree doubled in the representation.
proof:
label: Multiple Degree Doubling Nodes

content: Let $u_i \in R_i$ be a node such that for some parent $u_{p_1} \in R_{i-1}$, the interior degree condition fails: \[ |\text{int}(u_{p1}, u_i)| < i. \] Then the same condition fails for every other parent $u_{p_2} \in R_{i-1}$, implying that every node in $R_{i-1}$ is a degree-doubling node.
proof: Suppose, for contradiction, there exists a node $u_i \in R_i$ and a parent $u_{p_1} \in R_{i-1}$ with \[ |\text{int}(u_{p_1},u_i)| \delta -i \geq |N^+(u_{p_2})|. \] Therefore, \[ |N^{++}(u_{p_2})| \geq |N^+(u_{p_2})|, \] which means $u_{p_2}$ is a degree-doubling node, violating the DNSP.

Since this argument holds for $u_{p_2} \in R_{i-1}$, all parents of $u_i$ fail the interior degree condition, and thus all become degree-doubling nodes.
label: One Interior Fail Means All Fail

content: Suppose that for a node $u_{p_1} \in R_{i-1}$ and every $u_i \in R_i$ the interior degree condition holds: \[ |\text{int}(u_{p_1}, u_i)| \geq i. \] Then this condition holds for all other parents $u_{p_2} \in R_{i-1}$, and no node in $R_{i-1}$ is degree doubling.
proof: Assume that for a particular parent node $u_{p_1} \in R_{i-1}$, the interior arc condition holds for every child node $u_i \in R_i$: \[ |\text{int}(u_{p1},u_i)|\geq i. \] By definition, this implies that each such node $u_i$ sends at most $\delta - i$ arcs to the next neighborhood $R_{i+1}$, i.e., \[ |\text{ext}(u_i,R_{i+1})| < \delta -i. \] Now, for any other parent $u_{p_2} \in R_{i-1}$, We want to show that for every shared child $u_i$, the interior condition also holds for $u_{p_2}$.\\ \[ N^{++}(u_{p_2}) \subseteq \bigcup_{u_i \in N^+(u_{p_2})} \text{ext}(u_i, R_{i+1}). \] Since each $u_i$ sends at most $\delta -i$ arcs to $R_{i+1}$, and by Lemma (Formula for Rooted Neighborhood Size), the size of $R_{i+1}$ is also bounded by $\delta - i$, it follows that \[ |N^{++}(u_{p2})| \leq |N^+(u_{p_2})| \times (\delta - i) \leq |N^+(u_{p_2}| \times 1, \] where the factor 1 applies if the out-degree matches the bound tightly. More precisely, the cardinality of second out-neighbors does not exceed that of first out-neighbors.

Hence, \[ |N^{++}(u_{p_2})| < |N^+(u_{p_2})|, \] and $u_{p_2}$ is not a degree-doubling node.

Working backward, since this holds for all $u_{p_2}\in R_{i-1}$, the interior degree condition \[ |\text{int}(u_{p_2}, u_i)| \geq i. \] must hold for all parents $u_{p_2}$ and children $u_i$.
label: One Interior Succeed Means All Succeed

content: Suppose we have a graph $G$. The Decreasing Neighborhood Sequence Property Algorithm has a complexity of $O(|V| + |E|)$, where $|V|$ represents the number of vertices in $G$ and $|E|$ represents the number of edges in $G$.
proof: We need to analyze the complexity in two main phases: constructing the partitions $R_0,R_1,\ldots,R_k$, and running the core Decreasing Neighborhood Sequence Property checks.

Finding a node $v_0 \in G$ of minimum out-degree requires scanning all vertices and their out-degrees. This involves $O(|V|)$ operations, assuming out-degree is accessible efficiently.

Partitioning vertices into sets $R_i$ based on their out-distance from $v_0$ involves traversing edges to identify neighbors layer-by-layer. Since each edge is considered at most once in the breadth-first style partitioning, the partitioning phase takes $O(|V|+|E|)$.

Next we begin the analysis of the complexity of the algorithm. By Lemma (Interior Degrees Doubles), each neighborhood $R_i$ contains at least one node whose interior degree doubles. This guarantees the existence of degree-doubling nodes without exhaustively checking every node, allowing early termination in many cases. This is known to be true with $O(1)$ knowledge, i.e. we do not need to check any neighborhood before knowing that a node has their interior degree double.

The total number of neighborhoods $k$ is bounded by $|V|$ because each vertex appears in exactly one partition $R_i$.

Processing each neighborhood involves checking arcs and node degrees, each bounded by $O(|V|+|E|)$ collectively over all partitions.

Thus, the overall complexity of the algorithm, including partition construction and checks for degree doubling, is \[ O(|V|)+O(|V|+|E|)+O(|V|+|E|)=O(|V|+|E|) \] This linear complexity holds for any oriented graph $G$.
label: Proof of Complexity of Algorithm

content: Example to show how Partitions and influencer nodes can help with network A/B testing.
proof:
label: GLOVER data structure in network A/B testing

content: Any dataset that can be represented in a structured encoding format (such as JSON, XML, YAML, or equivalent) can be represented using a GLOVER data structure, provided the user selects a valid metric. This will yield a valid GLOVER structure.
proof: Structured encoding formats, including JSON, XML, and YAML, encode data as discrete objects with finite fields and elements. Consequently, the number of elements in any dataset represented by these formats is finite, ensuring the data can be fully enumerated and partitioned. Let $M$ be the metric chosen by the user such as degree or distance in the Seymour Second Neighborhood Conjecture. $M$ is a field, attribute, or key present in the encoded data. $M$ corresponds to the basis for defining relationships across the neighborhoods. For each element $x$ in the dataset, the metric $M(x)$ determines a value or set of values that can be used to group elements. The dataset is partitioned into neighborhoods $R_1, R_2, ..., R_k$ based on $M$, where $R_i = \{x \mid M(x) = v_i\}$ for some value $v_i$. If $M$ improperly defines neighborhoods (e.g., allows elements to belong to multiple neighborhoods or leaves elements unassigned), then $M$ is not a valid metric. A valid $M$ ensures that all elements are correctly assigned to exactly one neighborhood. Thus, any dataset encoded in a structured format can be represented by a Graph Level Order data structure, provided a suitable metric $M$ exists.
label:

Note:
We’re continuously improving our visualizations to enhance your experience. Future updates will include additional visualizations, user interactions, and features like force-directed graphs. If you have feedback or suggestions, we’d love to hear from you! Stay tuned for updates.