146 Trees

146.1 Trees

Definition 146.1 An edge cut set: a set of edges whose deletion disconnects \(G\)

✓

An edge cut set: a set of edges whose deletion disconnects G.

For subsets S and S’ of V, [S, S’] denotes the set of edges with one end in S and the other in S’. An edge cut of G is a subset of E of the form [S, \(\bar{S}\)], where S is a nonempty proper subset of V and \(\bar{S}\) = V \ S.

Definition 146.2 A bond (§2.2): a minimal (nonempty) edge cut, i.e

✓

A bond (§2.2): a minimal (nonempty) edge cut, i.e. a minimal set of edges whose deletion disconnects G.

A minimal nonempty edge cut of G is called a bond; each cut edge e, for instance, gives rise to a bond {e}. If G is connected, then a bond B of G is a minimal subset of E such that G - B is disconnected.

Definition 146.3 The number of spanning trees \(\tau (G)\): the number of tree subgraphs \(T \le G\) on the full vertex set

✓

The number of spanning trees \(\tau \)(G): the number of tree subgraphs T \(\le \) G on the full vertex set.

We denote the number of spanning trees of G by \(\tau \)(G).

Definition 146.4 contract

Edge contraction G \(\cdot \) e (§2.4). Here it is stubbed on the same carrier V as a placeholder, purely so that the deletion–contraction recurrence (Theorem 2.8) can be typed.

An edge e of G is said to be contracted if it is deleted and its ends are identified; the resulting graph is denoted G \(\cdot \) e.

Theorem 146.5 Unique path between vertices in a tree

✓

Let \(G\) be a tree on a finite vertex set, and let \(u\) and \(v\) be any two of its vertices. Then there is exactly one path in \(G\) from \(u\) to \(v\); that is, among all walks from \(u\) to \(v\), precisely one has no repeated vertices.

Theorem 146.6 Edge count of a finite tree

✓

Let \(G\) be a finite simple graph that is a tree, meaning it is connected and contains no cycles. Then the number of edges of \(G\) is one less than the number of vertices; that is, if \(G\) has \(n\) vertices, then it has exactly \(n - 1\) edges.

Theorem 146.7 Every nontrivial finite tree has at least two leaves

✓

Let \(G\) be a tree on a finite vertex set \(V\) with at least two vertices. Then \(G\) has at least two leaves: there exist distinct vertices \(u, v \in V\) with \(\deg (u) = 1\) and \(\deg (v) = 1\).

Theorem 146.8 Characterization of bridges by cycles

✓

Let \(G\) be a finite simple graph and let \(v,w\) be two of its vertices. The edge \(\{ v,w\} \) is a bridge of \(G\) — that is, its removal increases the number of connected components — if and only if \(v\) and \(w\) are adjacent in \(G\) and the edge \(\{ v,w\} \) occurs in no cycle of \(G\).

Theorem 146.9 Trees as graphs whose edges are all bridges

✓

Let \(G\) be a connected finite simple graph. Then \(G\) is a tree — that is, connected and acyclic — if and only if every edge of \(G\) is a bridge, meaning that deleting it disconnects the graph (leaving its two endpoints in different connected components).

Theorem 146.10 Existence of a spanning tree

✓

Let \(G\) be a connected simple graph on a finite vertex set \(V\). Then there is a spanning subgraph \(T\) of \(G\) — a simple graph on the same vertex set \(V\) with \(T \le G\) — that is a tree, that is, \(T\) is connected and contains no cycle.

Theorem 146.11 Connected graphs have at least \(n-1\) edges

✓

Let \(G\) be a connected simple graph on a finite vertex set \(V\) with \(|V| = n\). Then the number of edges of \(G\) is at least \(n - 1\).

Theorem 146.12 Adding a non-tree edge creates a cycle

✓

Let \(G\) be a finite simple graph, and let \(T\) be a spanning tree of \(G\): a connected, acyclic subgraph of \(G\) that touches every vertex. If \(e\) is an edge of \(G\) that does not lie in \(T\), then the graph \(T + e\) obtained by adjoining \(e\) to \(T\) contains a cycle, i.e. there is a vertex \(u\) and a closed walk from \(u\) to itself in \(T + e\) that is a cycle.

Theorem 146.13 The unique bond in a cotree with one tree edge

✓

Let \(G\) be a finite connected graph, let \(T\) be a spanning tree of \(G\), and let \(e\) be an edge of \(T\). Write \(\bar T = E(G) \setminus E(T)\) for the cotree, the set of edges of \(G\) that lie outside \(T\). Then (i) no bond of \(G\) is contained in \(\bar T\), and (ii) there is exactly one bond of \(G\) contained in \(\{ e\} \cup \bar T\).

Theorem 146.14 Cut vertices of a tree are the non-leaf vertices

✓

Let \(G\) be a tree, that is, a finite connected acyclic graph, and let \(v\) be a vertex of \(G\). Then \(v\) is a cut vertex of \(G\) — meaning \(G\) is connected and deleting \(v\) (together with its incident edges) leaves a disconnected graph — if and only if the degree of \(v\) satisfies \(\deg (v) \gt 1\).

Theorem 146.15 Every connected graph has two non-cut vertices

✓

Let \(G\) be a finite connected simple graph with at least two vertices. Then \(G\) has two distinct vertices \(u\) and \(v\), neither of which is a cut vertex.

Theorem 146.16 Deletion–contraction for spanning trees

Let \(G\) be a finite graph, and write \(\tau (G)\) for its number of spanning trees, that is, the number of tree subgraphs of \(G\) on the full vertex set. If \(e\) is an edge of \(G\), then

\[ \tau (G) = \tau (G - e) + \tau (G \cdot e), \]

where \(G - e\) is the graph obtained by deleting \(e\) and \(G \cdot e\) is the graph obtained by contracting \(e\) (deleting it and identifying its two ends).

Theorem 146.17 Cayley’s formula for the number of spanning trees of the complete graph

✓

For every natural number \(n\), the number of spanning trees of the complete graph \(K_n\) on \(n\) vertices is \(\tau (K_n) = n^{n-2}\), where the exponent is the truncated difference (so it is \(0\) when \(n \lt 2\)).

Theorem 146.18 Existence of a minimum-weight spanning tree

✓

Let \(G\) be a connected simple graph on a finite vertex set \(V\), and let \(w\) assign a real weight \(w(e)\) to each unordered pair \(e\) of vertices. Then there exists a spanning subgraph \(T\) of \(G\) that is a tree and whose total edge weight \(\sum _{e \in E(T)} w(e)\) is least among all subgraphs \(T'\) of \(G\) that are trees.