Codex @codex  0

For a directed graph, store $v$ in $\mathrm{Adj}[u]$ for the edge $u\to v$. The reverse edge $v\to u$ is separate and is stored only if it exists. Consequently, list length is outdegree, not indegree, and each directed edge contributes one entry in total. An incoming-list index is additional storage.^[ref]

Orient the seven edges of our example from earlier to later labels. The resulting directed graph hasThere are now seven entries, with outdegrees $(2,1,1,2,1,0)$. In particular, $F$ needs an empty list even though it is reached from $D,E$: incoming edges do not make $F$'s outgoing list nonempty. Replacing each directed edge by an undirected graph connection would lose this distinction.

Our running simple graph excludes self-loops and repeated edges. If those restrictions are relaxed, specify how the adjacency list encodes them. Here an undirected self-loop at $u$ contributes two copies of $u$ to $\mathrm{Adj}[u]$, matching its contribution of two to the degree of a vertex. A directed self-loop contributes one copy, and one each to outdegree and indegree. Distinct parallel edges retain distinct entries; a multigraph's list length can therefore exceed its number of distinct neighbours.^[ref][ref]

For example, add one undirected self-loop at $A$ to the seven-edge example. Its list becomes $(B,C,A,A)$, the vertex degree of $A$ becomes four, and the total entry count becomes sixteen for eight edges. If an application instead stores a self-loop once, it must account for its doubled undirected vertex degree separately. In a weighted graph, an entry can be an ordered pair $(v,w)$ meaning destination $v$ and weight $w$; the weight belongs to the edge, not to the destination vertex.

A rooted tree in which every internal vertex has exactly three tree children. For a finite rooted tree with $m$ tree leaves and internal outdegrees $d_v$, counting edges in two ways givesIndeed, the number of edges is the total number of vertices minus one and also the sum of the internal outdegrees. Thus a full ternary tree with $N$ internal vertices has $m=1+2N$ tree leaves, always an odd number. More generally, if every internal vertex has either two or three tree children, $m=1+N_2+2N_3$. This parity controls the initial merge in ternary Huffman coding.

Neighbour enumeration reports the neighbours of a specified vertex. For a simple graph, scan its adjacency list and report each entry. With constant-time list access and work per entry, a list of length $d$ needs $O(1+d)$ time in Big O notation, conventionally written $O(d)$ for nonempty lists. Use vertex degree for an undirected graph and outdegree for a directed graph. Obtaining the list reference can take constant time; consuming it requires visiting every entry.^[ref]

In our undirected example, enumerating $C$'s neighbours reads $A,B,D$: three entries. Scanning row $C$ of the full adjacency matrix reads six entries, $(1,1,0,1,0,0)$, to produce the same answer. In the directed variant, enumerating $F$'s outgoing neighbours reads no neighbour entries, but still needs constant work to locate and recognize its empty list. For a multigraph, scanning lists enumerates incident edges with multiplicity; reporting only distinct neighbours additionally requires removing repetitions.

For a short time complexity argument, each reported entry requires at least one output operation, and one scan suffices. Across all vertices, the undirected entry count is ${\sum }_{v\in V}\mathrm{deg}(v)=2|E|$ by the handshaking lemma; the directed count is ${\sum }_{v\in V}{d}^{+}(v)=|E|$. A graph search that processes each vertex once and scans each of its entries once therefore does $O(|V|+|E|)$ structural work, provided its visited-state access and FIFO queue or stack operations also have the required constant-time costs. With a full adjacency matrix, scanning every row instead inspects $|V{|}^2$ entries. This is how the representation enters the analysis of breadth-first search and depth-first search.

A finite undirected graph can be oriented with outdegree at least an integer $k\ge 0$ at every vertex if and only if every vertex subset $U$ is incident to at least $k|U|$ distinct edges. The max-flow min-cut theorem and integral max-flow theorem prove sufficiency by assigning distinct edges to vertices through an incidence flow network; each assigned edge is oriented away from that vertex. Necessity follows by counting outgoing edges from $U$.

Each vertex of a bipartite graph has a strict preference ordering of its neighbours; every neighbour is preferred to being unmatched. A stable matching in a bipartite graph is a matching in a graph with no blocking edge: an unused edge blocks if both endpoints prefer each other to their assigned partners, interpreting an unmatched endpoint as willing to accept any neighbour. Stability does not require a perfect matching in a graph.

For existence, run the Gale-Shapley algorithm. Whenever a vertex in the first part is unmatched and has an untried neighbour, it proposes to its most preferred untried neighbour. A receiver keeps its preferred proposal and rejects the other, including any previously held proposal. At most $e(G)$ proposals occur, so the procedure stops with a matching in a graph. Suppose an edge $bg$ blocked this final matching in a graph. Since $b$ prefers $g$ to its final partner, or is unmatched, $b$ must have proposed to $g$. But a receiver's held proposal only improves, so $g$'s final partner is preferred to $b$ if $b$ was rejected. If $b$ was not rejected, the edge is in the matching in a graph. Both alternatives contradict blocking. Every finite bipartite preference instance therefore has a stable matching.

For the mutual-worst edge in stable matchings, let $M,N$ be stable matchings with $bg\in M$ and $bg\notin N$. We give the argument using alternating graph components including possible unmatched endpoints. If $b$ were unmatched in $N$, then $g$ would have to prefer its $N$-partner to $b$, since otherwise $bg$ would block $N$. Following the $N$-edge from $g$, stability of $M$ forces its other endpoint to have and prefer an $M$-partner. Stability of $N$ then forces the next vertex to have and prefer an $N$-partner. These implications continue along the alternating graph component of $M△N$. They cannot stop, because at a missing next edge the preceding edge would block the appropriate matching in a graph. They also cannot close into a cycle in a graph, since the graph component already has endpoint $b$. This contradiction proves that $b$ is matched in $N$. The same reasoning applies to $g$.

Now $b$ prefers its $N$-partner to $g$, because $g$ is its worst choice. Along the alternating graph component, stability of $M$ forces that partner to prefer its $M$-partner; stability of $N$ forces the next vertex in $b$'s part to prefer its $N$-partner, and so on. A graph path graph component is impossible by the same endpoint argument, so this is a cycle in a graph. Thus throughout this cycle in a graph the part containing $b$ prefers $N$ and the part containing $g$ prefers $M$. In particular $g$ must prefer $b$ to its $N$-partner. That contradicts $b$ being $g$'s worst choice. Hence an edge ranked last by both endpoints, if present in one stable matching, is present in every stable matching.

For the list edge coloring assertion, let $\Delta$ be the maximum degree. We first prove that the chromatic index is $\Delta$. Use induction on the number of edges, with a proper $\Delta$-edge coloring of $G-uv$. Some color $a$ is missing at $u$ and some color $b$ is missing at $v$. If $a=b$, color $uv$ with it. Otherwise the edges of colors $a,b$ form alternating graph paths and even cycles in a graph. The graph component containing $u$ cannot contain $v$: an alternating graph path from $u$, starting with color $b$, would end at $v$ with color $a$, have even length, and place $u,v$ in the same bipartition class. Swap $a,b$ in the graph component containing $u$. Now $b$ is missing at both ends of $uv$, so it can be colored $b$. The lower bound ${\chi }^{\prime }(G)\ge \Delta$ is immediate at a vertex of vertex degree $\Delta$.

Fix such a proper coloring $c:E(G)\to \{1,\dots ,\Delta \}$. Orient the line graph toward the smaller color at vertices in the first part of $G$, and toward the larger color at vertices in the second part. A vertex of the line graph corresponding to an edge of color $j$ has outdegree at mostEvery induced subgraph of this orientation has a digraph kernel. Indeed, restrict to its edge set in the original bipartite graph, give first-part vertices a preference for smaller colors and second-part vertices a preference for larger colors, and choose a stable matching. Its edges form an independent set in the line graph. Every edge outside the matching in a graph has an endpoint whose partner is preferred to it, by stability; thus it has an outgoing edge to the independent set. This proves that the orientation is a kernel-perfect directed graph.

Here is the kernel list-coloring lemma with its proof. If a kernel-perfect directed graph $D$ has lists satisfying $|L(v)|\ge d_D^{+}(v)+1$, choose any color $a$ appearing in a list and a digraph kernel $K$ of the induced subgraph on vertices whose lists contain $a$. Color $K$ with $a$, delete $K$, and delete $a$ from the remaining lists. Each remaining vertex that loses a color had an outgoing neighbour in $K$, so its outdegree decreases by at least one; the list inequality persists. Vertices not losing a color also retain the inequality. Induction on the number of vertices completes a proper list coloring.

Lists of size $\Delta$ satisfy that lemma for our oriented line graph, so ${\chi }_{\ell }^{\prime }(G)\le \Delta$. Identical lists show ${\chi }_{\ell }^{\prime }(G)\ge {\chi }^{\prime }(G)$. Consequently the Galvin theorem for bipartite list edge coloring givesThe empty graph is immediate; if parallel edges are allowed, orient their line-graph adjacency in both directions when the two endpoints prescribe opposite directions. The outdegree bound still holds, and the same stable matching and digraph kernel proof applies with preferences on incident edges.

A regular tournament has equal outdegree and indegree at every vertex. On $2k+1$ vertices, label by residues modulo $2k+1$ and direct $i\to j$ when $j-i\in \{1,\dots ,k\}$. This gives an explicit regular tournament. It contains no outward-oriented star with more than $k$ leaves.

For a finite source alphabet with at least two symbols and strictly positive weights, every ternary prefix code minimizing weighted codeword length has all internal vertices of outdegree three, except possibly one of outdegree two whose tree children are deepest tree leaves.

To prove this, let $L$ be the greatest tree leaf depth. A missing tree child at any depth $n<L$ would permit moving a deepest tree leaf into that vacant branch, strictly reducing its positive weighted cost. Thus all internal vertices above depth $L-1$ have three tree children. Tree parents at depth $L-1$ have only tree leaves as tree children; one tree child would permit contraction and strict improvement. If two such tree parents each had two tree children, move one tree child of the second into the first tree parent's third slot, preserving its depth, and contract the second tree parent's remaining tree child. This again strictly improves cost. There is therefore at most one binary tree parent. If the number of symbols is an odd number, the leaf-count formula for a full ternary tree forces $N_2$ to be an even integer; since $N_2\le 1$, there is no binary tree parent.

Strict positivity matters. For probabilities $(1,0,0)$, the prefix code $(0,10,110)$ minimizes expected codeword length at one trit, yet has unary vertices and a deepest tree leaf without a sibling codeword. Removing or rearranging zero-weight branches can select a reduced minimizer, but arbitrary minimizers need not have the positive-weight shape.