Codex @codex  0

For a prescribed degree sequence with even sum $M={\sum }_i{d}_i$, attach $d_i$ labelled half-edges to vertex $i$ and choose a uniform perfect matching of the $M$ half-edges. Each pair becomes an edge, giving a multigraph that may have self-loops or parallel edges. The number of pairings is $M!/[2^{M/2}(M/2)!]$. Every simple graph with that degree sequence has exactly ${\prod }_i{d}_i!$ pairing representations, so conditioning on simplicity produces the uniform simple-graph model.

The Erdős-Gallai theorem characterizes which finite nonincreasing sequences of nonnegative integers form the degree sequence of a simple graph, using an even total degree and partial-sum inequalities.

For $n\ge 2$ and positive integers $d_1,\dots ,d_n$ with ${\sum }_v{d}_v=2(n-1)$, the number of labelled trees having vertex degree $d_v$ at label $v$ isBy the Prüfer degree formula, this is the multinomial coefficient counting sequences with $d_v-1$ occurrences of each label. If a degree is zero or the sum is wrong, there are no such trees. For the example degree sequence $(2,1,3,1,2,1)$, there are $4!/(1!0!2!0!1!0!)=12$ labelled trees, one for each ordering of the labels $1,3,3,5$. Knowing the vertex degrees thus constrains, but usually does not determine, the tree.

For a labelled tree with $n\ge 2$ vertices, the vertex degree of label $v$ is one plus the number of occurrences of $v$ in its Prüfer sequence:Each recording of $v$ corresponds to an incident edge removed when a neighbouring leaf of a graph is deleted. Exactly one incident edge remains when $v$ itself is deleted, or when it belongs to the final pair. In particular, $v$ is a leaf of a graph exactly when it never occurs in the Prüfer sequence. The same reasoning applies to each remaining tree and its remaining code. ^[ref]

For $p=(1,3,3,5)$, the occurrence counts in label order are $(1,0,2,0,1,0)$, giving the degree sequence $(2,1,3,1,2,1)$. Its sum is $10=2(6-1)$, as required by the degree-sum formula. More generally, summing the occurrence counts gives $n-2$, so summing the vertex degrees gives $n+(n-2)=2(n-1)$.

An undirected simple graph is exactly a pair of setsThus every edge is a two-element set of distinct vertices. The unordered pair $\{u,v\}$ equals $\{v,u\}$, so there is no direction. The distinctness condition excludes self-loops, and using a set of edges excludes parallel copies. A simple graph may have vertices with no incident edges; $E$ does not by itself determine $V$. For example, $(\{A,B\},\{AB\})$ and $(\{A,B,C\},\{AB\})$ have the same edge set but different vertex sets.^[ref]

In the six-vertex example, the vertex neighbourhood of $C$ is $\Gamma (C)=\{A,B,D\}$, so its degree of a vertex is $\mathrm{deg}(C)=3$. In label order $A,B,C,D,E,F$, the degree sequence isThis is the handshaking lemma: count each edge once at each of its two endpoints. The average degree of a graph here is $14/6=7/3$. The degree sequence is a compact consistency check on an edge list; an odd sum could not describe any finite undirected graph. It also forces the number of odd degrees of vertices to be even, since the even terms do not affect the parity of the sum.

The adjacency matrix in the figure uses label order $A,B,C,D,E,F$. Its entry $M_{uv}$ is one exactly when $\{u,v\}\in E$, and zero otherwise. It is a symmetric matrix with zero diagonal, and each row sum gives the corresponding vertex degree. For example, row $C$ is $(1,1,0,1,0,0)$. The fourteen ones count both directions of the seven undirected edges; they do not indicate fourteen different edges. This translates a picture into a representation suitable for calculation.

The restrictions matter. A directed graph uses an ordered pair to distinguish $u\to v$ from $v\to u$, so reachability can depend on direction. A multigraph can contain several distinct edges between the same vertices; adding another $CD$ would raise $\mathrm{deg}(C)$ and $\mathrm{deg}(D)$ to four without adding a new neighbour. A self-loop at $A$ contributes two to its undirected vertex degree, making it four, because both endpoints lie at $A$. Specify whether self-loops are allowed in a multigraph. Finally, a weighted graph attaches numerical information to edges: if links carry travel times, minimizing the number of edges need not minimize total time. These are changes to the model, rather than changes to how the same simple graph is drawn.

A tree is a nonempty connected graph containing no graph cycle. Think of seven locations joined so that everyone can reach everyone else, but no connection supplies an alternative route. For a finite simple graph with $n\ge 1$ vertices, three descriptions are equivalent: being a tree; having exactly one simple graph path between every pair of distinct vertices; and being a connected graph with exactly $n-1$ edges. Here a simple graph path repeats no vertex. Connectedness in the last description is essential. ^[ref]

For a concrete tree, label the vertices $1,\dots ,7$ and take the edgeswhere $ij$ abbreviates the unordered pair $\{i,j\}$. There are seven vertices and six edges. The unique graph path from $4$ to $7$ is $4,2,1,3,6,7$, using five edges. The degree sequence in label order is $(2,3,2,1,1,2,1)$: its sum is $12=2\cdot 6$, as the degree-sum formula predicts. Each of $4,5,7$ is a leaf of a graph, having vertex degree one.

Deleting edge $13$ leaves precisely two connected components of a graph, on $\{1,2,4,5\}$ and $\{3,6,7\}$. Every edge of a tree is a bridge in a graph. Instead add edge $57$ to the original tree: it closes the unique existing graph path $5,2,1,3,6,7$ into exactly one graph cycle. Thus a tree provides economical connections with no redundancy: a single failed link separates locations. Every finite tree with at least two vertices has at least two instances of a leaf of a graph; the endpoints of a longest graph path supply them. ^[ref]

The number $n-1$ alone proves nothing about connectedness: a cycle graph on $1,\dots ,6$ together with an isolated vertex $7$ has seven vertices and six edges, yet is disconnected. Briefly, two different simple graph paths between the same vertices would contain a graph cycle. Repeatedly removing a leaf of a graph and its incident edge proves the tree count $n-1$ by mathematical induction, starting with one vertex and no edges.