Graph
We begin with the most fundamental object of study. A graph formalizes the idea of a collection of objects
(vertices) together with pairwise connections (edges) between them.
Definition: Graph
A graph is an ordered pair \(G = (V, E)\), where \(V\) is a finite set of
vertices (or nodes) and \(E \subseteq \binom{V}{2}\) is a set of
edges. Here \(\binom{V}{2}\) denotes the set of all 2-element subsets of \(V\),
so each edge is an unordered pair of two distinct vertices. We write \(V(G)\) for the vertex set
and \(E(G)\) for the edge set of \(G\).
Two consequences of the formal condition \(E \subseteq \binom{V}{2}\) are worth noting at the outset. First,
since 1-element subsets are excluded, no edge has the form \(\{x, x\}\). A graph has no loops
(edges joining a vertex to itself). Second, because \(E\) is a set, no two distinct edges can be the same
unordered pair, so there are no parallel edges. A graph in this sense is sometimes called a
simple graph for emphasis.
Convention. Throughout this page, the unqualified word "graph" means a finite,
undirected simple graph as defined above. Variants such as directed, weighted, and multigraphs
(introduced below) are used only when explicitly named.
The order of \(G\) is the number of its vertices:
\[
|G| = |V(G)|.
\]
Similarly, \(|E(G)|\) denotes the number of edges, sometimes called the size of \(G\).
A vertex \(v\) is incident with an edge \(e\) if \(v \in e\). We then say that \(e\) is an
edge at \(v\). The two vertices incident with an edge are its ends (or
endpoints), and an edge joins its ends. For brevity, an edge
\(\{x, y\} \in E(G)\) is typically written as \(xy \in E(G)\), with the understanding that \(xy\) and \(yx\)
denote the same edge.
Several important variants of the basic definition arise in practice, obtained by relaxing or modifying
the edge structure:
- Directed graph (digraph):
Each edge (often called an arc) has a direction from one vertex to another. Formally, edges
are ordered pairs:
\[
E \subseteq V \times V.
\]
In this generality, self-loops \((v, v)\) are typically permitted. A digraph forbidding them is
called a simple digraph.
- Weighted graph:
Each edge carries a numerical value (a "weight"), often representing cost, distance, or strength of connection.
A weighted graph is represented as
\[
G = (V, E, w),
\]
where \(w: E \to \mathbb{R}\) is a weight function. Weighted graphs are fundamental in shortest-path algorithms
and network optimization.
- Multigraph:
Multiple edges are allowed between the same pair of vertices. One common formulation is
\[
G = (V, E, \mu),
\]
where \(E \subseteq \binom{V}{2}\) and \(\mu: E \to \mathbb{Z}_{\geq 1}\) assigns a positive integer
multiplicity to each edge, the number of parallel edges joining its two ends. (Variants permitting loops
replace \(\binom{V}{2}\) with the larger set of unordered pairs allowing repetition. Multigraphs do not
feature in the main development of this page, so we leave the precise variant unspecified.)
The local structure around each vertex comes next: adjacency and neighborhoods.
Neighbors
Adjacency, the most basic local property of a graph, records which vertices are directly joined by an edge.
From adjacency, we derive neighborhoods, independence, and edge-counting between vertex subsets.
Definition: Adjacency and Neighborhood
Two vertices \(x, y \in V(G)\) are adjacent (or neighbors) if
\(xy \in E(G)\). The neighborhood of a vertex \(x\) is the set
\[
N_G(x) = \{ y \in V(G) : xy \in E(G) \},
\]
often written simply as \(N(x)\) when the graph \(G\) is clear from context.
Definition: Complete Graph
A graph \(G\) is complete if every pair of distinct vertices is adjacent.
The complete graph on \(n\) vertices is denoted \(K_n\). For example, \(K_3\) is the triangle.
Similarly, two edges \(e \neq f\) are adjacent if they share a common endpoint.
A set of vertices (or edges) is called independent if no two of its elements are adjacent.
It is often useful to count edges within and between subsets of vertices. For any subset \(A \subseteq V(G)\),
we define \(e(A)\) as the number of edges with both endpoints in \(A\). More generally, given two subsets
\(A, B \subseteq V(G)\), we define
\[
e(A, B) = |\{ (a, b) \in A \times B : ab \in E(G) \}|.
\]
Since \(e(A, B)\) counts ordered pairs, an edge \(uv \in E(G)\) with \(u \in A\) and \(v \in B\) is
counted once via the pair \((u, v)\). The same edge is also counted via \((v, u)\) precisely when both
\(u, v \in A \cap B\). Edges with both endpoints in \(A \cap B\) are therefore counted twice, while all other
edges between \(A\) and \(B\) are counted once. Two consequences are worth recording:
-
Taking \(B = A\) gives \(e(A, A) = 2\, e(A)\), since every edge with both endpoints in \(A\) is
counted twice (once as \((a, b)\) and once as \((b, a)\)).
-
When \(A\) and \(B\) are disjoint, \(e(A, B)\) counts exactly the edges crossing between the two parts.
This quantity is central to the study of bipartite graphs and graph cuts.
Adjacency tells us which vertices are connected. The natural next question is: how many connections
does each vertex have? This leads us to the concept of degree.
Degrees
The degree of a vertex quantifies how "connected" it is within the graph. This simple count is one of the most
informative local invariants, and it leads immediately to the Handshaking Lemma, a fundamental identity that
constrains the global structure of any graph.
Definition: Degree
For a simple graph \(G\), the degree of a vertex \(x\) is the number of its neighbors:
\[
\deg_G(x) = |N_G(x)|,
\]
written simply as \(\deg(x)\) when \(G\) is understood. For directed graphs, we distinguish the
in-degree \(\deg^-(x)\) (the number of edges directed into \(x\)) and the
out-degree \(\deg^+(x)\) (the number of edges directed out of \(x\)).
Definition: Degree Sequence
The degree sequence of a graph \(G\) on \(n\) vertices is the multiset
\(\{\deg(v_1), \deg(v_2), \ldots, \deg(v_n)\}\) of vertex degrees, conventionally listed
in non-increasing order:
\[
d_1 \geq d_2 \geq \cdots \geq d_n,
\]
where \(d_i = \deg(v_i)\) under some ordering of the vertices. Because the multiset itself does not depend
on how the vertices are labeled, the degree sequence is an intrinsic feature of \(G\). We revisit this
property when we discuss isomorphism invariants.
The minimum degree and maximum degree of a non-empty graph \(G\) are denoted respectively by
\[
\delta(G) = \min_{x \in V} \deg(x), \quad \Delta(G) = \max_{x \in V} \deg(x).
\]
The average degree of such a graph, written \(d(G)\), satisfies the natural inequality
\[
\delta(G) \leq d(G) \leq \Delta(G).
\]
Definition: \(k\)-Regular Graph
A graph \(G\) is \(k\)-regular if every vertex has the same degree \(k\). Equivalently,
\(\delta(G) = \Delta(G) = k\). A graph is regular if it is \(k\)-regular for some \(k\).
For example, the complete graph \(K_n\) is \((n-1)\)-regular, every cycle \(C_n\) is \(2\)-regular, and the
cube graph \(Q_3\) (the \(1\)-skeleton of the 3-cube) is \(3\)-regular. Regularity is a strong structural
constraint that simplifies many counting arguments and is central to spectral graph theory.
Proposition: Handshaking Lemma
For any graph \(G = (V, E)\),
\[
\sum_{x \in V} \deg(x) = 2|E|.
\]
Proof:
An incidence is a pair \((x, e) \in V \times E\) with \(x \in e\). We count incidences in two ways. For
each vertex \(x \in V\), the edges incident to \(x\) are exactly the edges \(xy\) with \(y \in N(x)\),
and \(y \mapsto xy\) is a bijection from \(N(x)\) onto them. Their number is therefore \(\deg(x)\), and
summing over all vertices gives \(\sum_{x \in V} \deg(x)\). On the other hand, each edge
\(e = xy \in E\) has exactly two endpoints, so it contributes \(2\) to the total count of incidences.
Equating the two counts yields
\[
\sum_{x \in V} \deg(x) = 2|E|.
\]
Extension to Multigraphs
The Handshaking Lemma extends to multigraphs (and to graphs with loops) once the degree is redefined. We
let \(\deg(v)\) count the edge-ends at \(v\), so each parallel edge between \(u\) and \(v\) contributes one
to each of its ends, and each loop at \(v\) contributes \(2\) to \(\deg(v)\). With incidences counted as
edge-ends, every edge still has exactly two ends, and the double count in the proof above goes through
verbatim. This generality is occasionally useful. Road networks with multiple direct connections call for
it, as do classical formulations of Eulerian cycles, where parallel edges arise naturally
(Königsberg's seven bridges being the historical prototype).
For a non-empty graph, defining \(\varepsilon(G) = |E|/|V|\), the number of edges per vertex, we can
rewrite the Handshaking Lemma as
\[
d(G) = \frac{1}{|V|}\sum_{x \in V}\deg(x) = \frac{2|E|}{|V|} = 2\,\varepsilon(G).
\]
This identity connects the average degree to the edge-to-vertex ratio \(\varepsilon(G)\). The same degree sum
reappears in the graph Laplacian. Its
diagonal entries are the vertex degrees, so its trace equals \(\sum_{x \in V} \deg(x) = 2|E|\).
Corollary: Number of Odd-Degree Vertices is Even
In any graph \(G = (V, E)\), the number of vertices of odd degree is even.
Proof:
Partition \(V\) into the set \(V_{\mathrm{odd}}\) of vertices of odd degree and the set
\(V_{\mathrm{even}}\) of vertices of even degree. By the Handshaking Lemma,
\[
\sum_{x \in V_{\mathrm{odd}}} \deg(x) + \sum_{x \in V_{\mathrm{even}}} \deg(x) = 2|E|.
\]
The right-hand side is even, and the second sum on the left is a sum of even integers, hence even.
Therefore the first sum, \(\sum_{x \in V_{\mathrm{odd}}} \deg(x)\), is also even. Writing each odd term as
\(\deg(x) = 2 k_x + 1\) for some \(k_x \in \mathbb{Z}_{\geq 0}\), we obtain
\[
\sum_{x \in V_{\mathrm{odd}}} \deg(x) = 2 \sum_{x \in V_{\mathrm{odd}}} k_x + |V_{\mathrm{odd}}|.
\]
The left-hand side is even and the first term on the right is even, so \(|V_{\mathrm{odd}}|\) must be
even as well.
This innocent-looking corollary has surprisingly broad consequences. It underpins parity arguments throughout
graph theory, including the degree-parity criteria for
Eulerian cycles and paths.
Insight: Vertex Degree in Graph-Based ML
Vertex degree is more than a counting tool. It is a first-order structural feature that pervades
graph-based machine learning. The degree matrix \(D\), the diagonal matrix with
\(D_{ii} = \deg(v_i)\), is a building block of both the
graph Laplacian \(L = D - A\), where
\(A\) is the
adjacency matrix, and its
normalized variants used in
spectral clustering. In
Graph Neural Networks (GNNs), the degree appears explicitly in the symmetric
normalization \(D^{-1/2}AD^{-1/2}\) that prevents high-degree "hub" nodes from dominating the
message-passing aggregation. In practice a self-loop is first added at every vertex, so that no degree
vanishes and \(D^{-1/2}\) exists. Even the simple degree sequence of a graph can serve as a powerful
feature for graph classification tasks.
The degree sequence is one example of a graph invariant, a quantity preserved by isomorphism. This
observation leads naturally to the question: when should two graphs be considered "the same"?
Isomorphism
Two graphs may look different when drawn on paper yet have identical structure. Isomorphism
makes this idea precise. Two graphs are "the same" when we can relabel the vertices of one to obtain the other
while preserving all edge relationships.
Definition: Graph Isomorphism
Two graphs \(G = (V, E)\) and \(G' = (V', E')\) are isomorphic, written \(G \simeq G'\),
if there exists a bijection \(\varphi: V \to V'\) such that
\[
\forall\, x, y \in V \text{ with } x \neq y, \quad xy \in E \iff \varphi(x)\varphi(y) \in E'.
\]
Such a map \(\varphi\) is called an isomorphism. An automorphism of
\(G\) is an isomorphism from \(G\) to itself, that is, a bijection \(\varphi: V(G) \to V(G)\) preserving
edges and non-edges.
Note that the condition is a biconditional (\(\iff\)). The map \(\varphi\) must preserve edges and
non-edges. A bijection that maps edges to edges but creates spurious new edges is not an isomorphism.
Isomorphism naturally gives rise to two important concepts, often used in tandem to classify graphs
and to certify non-isomorphism.
Definition: Graph Property and Graph Invariant
A graph property is a class \(\mathcal{P}\) of graphs that is closed under isomorphism. If
\(G \in \mathcal{P}\) and \(G \simeq G'\), then \(G' \in \mathcal{P}\). A graph invariant
is a function \(f\) defined on graphs such that \(G \simeq G'\) implies \(f(G) = f(G')\).
The two notions are intertwined. Every graph property \(\mathcal{P}\) gives rise to its indicator invariant
\(\mathbf{1}_{\mathcal{P}}\), and every invariant \(f\) partitions graphs into properties by the level sets
\(\{G : f(G) = c\}\). For example, containing a triangle (a
cycle of length 3) is a graph property. If \(G\)
contains a triangle, then so does every graph isomorphic to \(G\). Familiar invariants include the number of
vertices, the number of edges, and the
degree sequence. The first is invariant
because an isomorphism \(\varphi\) is a bijection on vertices. For the other two, the biconditional in the
definition shows that \(\varphi\) maps \(N_G(x)\) bijectively onto \(N_{G'}(\varphi(x))\), so
\(\deg_{G'}(\varphi(x)) = \deg_G(x)\) for every vertex \(x\). The degree multisets therefore agree, and the
Handshaking Lemma then gives
\(|E(G)| = |E(G')|\). Invariants are the primary tool for proving that two graphs are not isomorphic.
If any invariant differs, the graphs cannot be isomorphic.
Isomorphism tells us when two graphs are structurally identical. The complementary notion is the subgraph,
which lets us identify and analyze the parts of a single graph.
Subgraphs
Just as subsets and subspaces play a central role in set theory and linear algebra, subgraphs allow us
to study the local and partial structure of a graph. We first note that set-theoretic operations extend naturally to graphs.
Given two graphs \(G = (V, E)\) and \(G' = (V', E')\), we define
\[
G \cup G' = (V \cup V',\, E \cup E'), \quad G \cap G' = (V \cap V',\, E \cap E').
\]
If \(V \cap V' = \emptyset\) (and hence \(E \cap E' = \emptyset\)), the graphs are said
to be disjoint.
Definition: Bipartite Graph
A graph \(G = (V, E)\) is bipartite if its vertex set can be partitioned into two
(possibly empty) parts \(U\) and \(W\) such that every edge has one endpoint in \(U\) and the other
in \(W\). Formally,
\[
E \subseteq \{\,\{u, w\} : u \in U,\, w \in W\,\}.
\]
Equivalently, no edge joins two vertices within the same part. The pair \((U, W)\) is called a
bipartition of \(G\).
Bipartite graphs arise naturally in matching problems (for example, assigning jobs to applicants) and are
characterized by the absence of odd-length cycles. The
characterization theorem appears
later in this page.
Definition: Complete Bipartite Graph
For positive integers \(m, n \geq 1\), the complete bipartite graph \(K_{m,n}\) is the
bipartite graph with parts \(U\) of size \(m\) and \(W\) of size \(n\) in which every vertex of \(U\) is
adjacent to every vertex of \(W\). Formally,
\[
E(K_{m,n}) = \{\,\{u, w\} : u \in U,\, w \in W\,\}.
\]
Thus \(K_{m,n}\) has \(m + n\) vertices and \(mn\) edges. Familiar instances include \(K_{1,n}\) (the
star graph with \(n\) edges) and \(K_{3,3}\) (the utility graph, which will play a
central role when we study planarity).
Definition: Vertex Deletion and Edge Addition
Let \(G = (V, E)\) be a graph.
-
For a vertex \(v \in V\), the vertex-deleted graph \(G - v\) is obtained by removing
\(v\) from \(V\) and all edges incident to \(v\) from \(E\):
\[
G - v = \bigl(V \setminus \{v\}, \{e \in E : v \notin e\}\bigr).
\]
-
For distinct vertices \(x, y \in V\) with \(xy \notin E\), the
edge-added graph \(G + xy\) is the graph \(\bigl(V, E \cup \{xy\}\bigr)\).
Definition: Subgraph, Induced Subgraph, and Spanning Subgraph
Let \(G = (V, E)\) and \(G' = (V', E')\) be graphs.
-
\(G'\) is a subgraph of \(G\) (written \(G' \subseteq G\)) if \(V' \subseteq V\) and \(E' \subseteq E\).
In this case, \(G\) is a supergraph of \(G'\).
-
\(G'\) is an induced subgraph of \(G\) if \(G' \subseteq G\) and \(G'\) contains
every edge of \(G\) both of whose endpoints lie in \(V'\):
\[
G' = G[V'] = \bigl(V', \{xy \in E : x, y \in V'\}\bigr).
\]
-
\(G'\) is a spanning subgraph of \(G\) if \(G' \subseteq G\) and \(V' = V\), that is,
\(G'\) has the same vertex set as \(G\) but possibly fewer edges.
The distinction between a general subgraph and an induced subgraph is important. A subgraph may omit edges
between vertices it retains, while an induced subgraph must include all such edges. We will see a concrete
example illustrating this distinction at the end of this page.
Finally, a graph \(G\) is said to be edge-maximal with respect to a given graph property
if \(G\) has the property, but adding any new edge between non-adjacent vertices destroys it. That is,
\(G + xy\) fails to have the
property for every pair of distinct non-adjacent vertices \(x, y \in V(G)\).
Subgraphs describe the "parts" of a graph. Paths and cycles describe how to traverse one.
Paths & Cycles
Paths and cycles are arguably the most fundamental structures in graph theory. A path captures the idea
of "getting from \(A\) to \(B\) without repeating vertices," while a cycle represents a closed traversal.
Together, they underpin connectivity, shortest-path algorithms, and the classification of graphs by their cycle structure.
Definition: Path
A path is a non-empty graph \(P = (V, E)\) of the form
\[
V = \{x_0, x_1, x_2, \ldots, x_k\}, \quad E = \{x_0 x_1,\, x_1 x_2,\, \ldots,\, x_{k-1} x_k\},
\]
where all vertices \(x_0, x_1, \ldots, x_k\) are distinct and \(k \geq 0\). The vertices \(x_0\) and
\(x_k\) are the ends of \(P\). The remaining vertices are its
inner vertices. The length of a path is its number of edges, namely
\(k\). In the boundary case \(k = 0\), the path consists of a single vertex with no edges. It has length
\(0\), and its sole endpoint serves as both \(x_0\) and \(x_k\).
By convention, \(P_k\) denotes the path on \(k\) vertices (and hence \(k - 1\) edges).
For example, \(P_4\) has 4 vertices and 3 edges.
(Note: In some literature, the index \(k\) refers to the path's length (number of edges).
We consistently use the vertex-count convention here.)
Definition: Cycle
For \(m \geq 3\), if \(P = x_0 x_1 \cdots x_{m-1}\) is a path on \(m\) vertices, then the graph
obtained by adding the edge \(x_{m-1} x_0\) is called an \(m\)-cycle, denoted
\(C_m\). An \(m\)-cycle has \(m\) vertices and \(m\) edges. The integer \(m\) is the
length of the cycle.
For example, \(C_3\) is a triangle (3 vertices, 3 edges), and \(C_4\) is a square (4 vertices, 4 edges).
Definition: Connected Graph
A non-empty graph \(G = (V, E)\) is connected if for every pair of distinct vertices
\(x, y \in V\) there exists a path in \(G\) from \(x\) to \(y\). Equivalently, the binary relation on
\(V\) defined by "\(x \sim y\) iff there is a path from \(x\) to \(y\)" is an equivalence relation
whose equivalence classes number exactly one. These classes are the
connected components of \(G\).
The "equivalent" formulation requires a brief check, and the check uses one auxiliary notion. A
walk from \(x\) to \(z\) is a sequence of vertices \(x = w_0, w_1, \ldots, w_L = z\) in which
consecutive vertices are adjacent. Unlike a path, a walk may repeat vertices and edges. Its length is \(L\),
and it is closed if \(w_L = w_0\). Walks are developed further, together with trails, in
walks and trails. Reflexivity is
the trivial path of length \(0\) at \(x\). Symmetry holds because every path can be traversed in reverse.
Transitivity follows because the concatenation of a path from \(x\) to \(y\) and a path from \(y\) to \(z\) is
a walk from \(x\) to \(z\), and any walk between two vertices contains a path between them (by repeatedly
shortcutting at any vertex visited more than once).
We also use the name component for the subgraph \(G[C]\) induced by an equivalence class
\(C\). Each component is connected, because every vertex on a path from \(x\) to \(y\) is equivalent to
\(x\), so the path stays inside the class. Every edge \(xy\) of \(G\) lies in exactly one component, since
\(x\) and \(y\) are joined by a path of length \(1\). In particular, no edge joins two distinct components.
Connectivity will be the standing hypothesis whenever we discuss spanning structures, traversal problems,
or component-wise decompositions.
Definition: Acyclic Graph, Forest, and Tree
A graph that contains no cycle is called acyclic. Such a graph is also called a
forest. A connected acyclic graph is called a tree. Equivalently, the
connected components of a forest are themselves trees.
Trees admit several powerful equivalent characterizations. To prepare the way, we first record a lower bound on
the number of edges in a connected graph.
Lemma: Edge-Count Lower Bound for Connected Graphs
Any connected graph on
\(n \geq 1\) vertices has at least \(n - 1\) edges.
Proof:
Induction on \(n\). The base case \(n = 1\) is immediate (\(0 \geq 0\)). For \(n \geq 2\), let
\(G\) be a connected graph on \(n\) vertices and pick any vertex \(v \in V(G)\). Since \(G\) is
connected and \(n \geq 2\), we have \(\deg_G(v) \geq 1\). Let \(H = G - v\), the
vertex-deleted graph. The
graph \(H\) has \(c\) connected components \(H_1, \ldots, H_c\) on \(n_1, \ldots, n_c\)
vertices, with \(\sum_i n_i = n - 1\).
Because \(G\) itself is connected, \(v\) must have at least one neighbor in each component \(H_i\).
Otherwise no edge of \(G\) would join \(H_i\) to a vertex outside it, since \(H\) has no edges between
distinct components and \(v\) has no neighbor in \(H_i\). A path in \(G\) from \(v\) to a vertex of \(H_i\)
would then have no edge by which to enter \(H_i\), contradicting connectivity of \(G\). Hence
\(\deg_G(v) \geq c\). Each \(H_i\) is connected and has \(n_i \lt n\) vertices, so the induction hypothesis
gives \(|E(H_i)| \geq n_i - 1\). Every edge of \(G\) either lies in \(H\), and hence in exactly one
\(H_i\), or is one of the \(\deg_G(v)\) edges at \(v\). Summing,
\[
\begin{align*}
|E(G)| &= \sum_{i=1}^{c} |E(H_i)| + \deg_G(v) \\\\
&\geq \sum_{i=1}^{c} (n_i - 1) + c \\\\
&= (n - 1 - c) + c \\\\
&= n - 1.
\end{align*}
\]
With this lemma in hand, we can state and prove the central characterization theorem.
Theorem: Characterizations of Trees
Let \(T = (V, E)\) be a graph on \(n \geq 1\) vertices. The following are equivalent:
- \(T\) is a tree (connected and acyclic).
- For every pair of vertices \(x, y \in V\), there is a unique path in \(T\) from \(x\) to \(y\).
- \(T\) is connected and has exactly \(n - 1\) edges.
- \(T\) is acyclic and has exactly \(n - 1\) edges.
Proof:
We prove (1) \(\Rightarrow\) (2) \(\Rightarrow\) (3) \(\Rightarrow\) (4) \(\Rightarrow\) (1).
(1) \(\Rightarrow\) (2). By connectedness, between any two vertices \(x, y\) there exists
at least one path. Suppose for contradiction that there are two distinct paths \(P_1, P_2\) from \(x\) to
\(y\). Let \(u\) be the last vertex up to which \(P_1\) and \(P_2\) coincide when traversed from \(x\).
That is, the next vertex on \(P_1\) after \(u\) differs from the next vertex on \(P_2\) after \(u\). Let
\(v\) be the first vertex after \(u\) on \(P_1\) that also appears on \(P_2\). Such a \(v\) exists because
both paths end at \(y\).
The portion of \(P_1\) from \(u\) to \(v\) and the portion of \(P_2\) from \(u\) to \(v\) share only the
endpoints \(u\) and \(v\) (by the choice of \(v\) as the first re-meeting point), so their internal
vertices are disjoint. Concatenating one with the reverse of the other yields a closed walk in which all
vertices are distinct except that the start equals the end. If both \(u\)-\(v\) segments had length \(1\),
each would be the single edge \(uv\). In our simple-graph setting there is at most one such edge, so
\(P_1\) and \(P_2\) would agree at this step, contradicting the choice of \(u\) as a divergence point.
Hence at least one segment has length \(\geq 2\), so the resulting closed walk traverses at least three
distinct vertices in cyclic order. It is therefore a
cycle. This contradicts acyclicity.
(2) \(\Rightarrow\) (3). Uniqueness of paths trivially implies connectedness. We show
\(|E| = n - 1\) by induction on \(n\). The case \(n = 1\) is immediate (no edges). For \(n \geq 2\),
observe that \(T\) must contain a vertex of degree \(1\). Pick any longest path \(x_0 x_1 \cdots x_p\) in
\(T\). Since \(T\) is connected and \(n \geq 2\), it has an edge, so \(p \geq 1\). The endpoint \(x_p\)
cannot have a neighbor outside the path (else the path could be extended) nor a second neighbor on the path
(else two distinct paths from \(x_p\) to that neighbor would exist, contradicting (2)). So
\(\deg(x_p) = 1\).
Removing \(x_p\) and its incident edge yields a graph \(T'\) on \(n - 1\) vertices. A path of \(T\) between
two vertices of \(T'\) cannot pass through \(x_p\), because an inner vertex of a path has two neighbors on
it. The paths of \(T'\) are therefore exactly the paths of \(T\) avoiding \(x_p\), so \(T'\) inherits both
the existence and the uniqueness in (2). By induction \(|E(T')| = n - 2\), hence \(|E(T)| = n - 1\).
(3) \(\Rightarrow\) (4). Suppose \(T\) is connected with \(n - 1\) edges. We
must show \(T\) is acyclic. If \(T\) contained a cycle \(C\), pick any edge \(e \in E(C)\). Then
\(T - e\) (the graph obtained by removing the edge \(e\), keeping all vertices) is still
connected. The two endpoints of \(e\) remain joined by the rest of the cycle, and any path in
\(T\) using \(e\) can be re-routed around the cycle. But \(T - e\) has \(n\) vertices and
\(n - 2\) edges, contradicting the
edge-count lower bound
for connected graphs.
(4) \(\Rightarrow\) (1). Suppose \(T\) is acyclic with \(n - 1\) edges. Decompose \(T\)
into its connected components \(T_1, \ldots, T_c\), with \(|V(T_i)| = n_i\) and \(\sum n_i = n\). Each
\(T_i\) is connected and acyclic, hence itself a tree on \(n_i\) vertices. By the already-proved chain (1)
\(\Rightarrow\) (2) \(\Rightarrow\) (3) applied to each \(T_i\), we have \(|E(T_i)| = n_i - 1\). Summing,
\[
|E(T)| = \sum_{i=1}^{c} (n_i - 1) = n - c.
\]
Since \(|E(T)| = n - 1\), we conclude \(c = 1\), so \(T\) is connected, hence a tree.
Trees are among the most ubiquitous structures in both mathematics and computer science, from parse trees in
compilers to decision trees in machine learning. We study them in greater depth, including rooted trees and
spanning trees, in Trees and Enumeration.
Theorem: Bipartiteness via Odd Cycles
A graph \(G\) is bipartite if
and only if it contains no cycle of odd length.
Proof:
(\(\Rightarrow\)) Suppose \(G\) is bipartite with parts \(U, W\) and let
\(C = x_0 x_1 \cdots x_{k-1} x_0\) be any cycle in \(G\). Since every edge of \(C\) joins \(U\) to \(W\),
the vertices \(x_0, x_1, x_2, \ldots\) alternate between the two parts. Say \(x_0 \in U\). To return to
\(x_0\) after \(k\) steps, we need an even number of crossings, so \(k\) is even.
(\(\Leftarrow\)) Suppose \(G\) contains no odd cycle. Without loss of generality assume
\(G\) is connected (otherwise apply the argument to each connected component and take the union of the
bipartitions). Fix a vertex \(r \in V\) and define
\[
U = \{\, v \in V : \text{shortest-path distance from } r \text{ to } v \text{ is even}\,\},
\quad
W = V \setminus U.
\]
We claim \((U, W)\) is a valid bipartition, that is, no edge has both endpoints in the same part. Suppose
otherwise, so that an edge \(uv \in E\) has \(u, v \in U\) (the case \(u, v \in W\) is analogous). Then the
distances \(d(r, u)\) and \(d(r, v)\) are both even. Concatenating a shortest path from \(r\) to \(u\), the
edge \(uv\), and the reverse of a shortest path from \(r\) to \(v\), we obtain a closed walk of length
\(d(r, u) + 1 + d(r, v)\), which is odd.
It remains to show that any closed walk of odd length contains an odd cycle, which then contradicts the
hypothesis. We argue by induction on the length \(L\) of the closed walk \(w_0, w_1, \ldots, w_L\) with
\(w_L = w_0\). Since \(G\) has no loops, \(L \neq 1\), so the odd length \(L\) is at least \(3\). An
internal repetition is a pair \(i \lt j\) with \(w_i = w_j\) other than \((i, j) = (0, L)\). If
the walk has none, then \(w_0, \ldots, w_{L-1}\) are distinct and \(L \geq 3\), so the walk traces a cycle
of odd length.
Otherwise, locate the first internal repetition \(w_i = w_j\) with \(i \lt j\). Splitting at this
repetition yields two strictly shorter closed walks. The inner segment \(w_i, w_{i+1}, \ldots, w_j\) has
length \(j - i\), and the outer segment \(w_0, \ldots, w_i, w_{j+1}, \ldots, w_L\) has length
\(L - (j - i)\). Their lengths sum to \(L\), which is odd, so exactly one of them is odd. By the induction
hypothesis applied to that shorter odd closed walk, an odd cycle exists.
This characterization is the cornerstone of bipartite-graph algorithms. Testing bipartiteness reduces to a
depth-first or breadth-first search that 2-colors the graph and checks every non-tree edge for a color
conflict, an \(O(|V| + |E|)\) procedure. The odd-cycle obstruction reappears in the study of
planar graphs and of
random walks on graphs.
Paths, Cycles, and Trees in CS and ML
These three structures are the foundation of algorithmic graph theory. Shortest paths
(Dijkstra's algorithm, Bellman-Ford) power routing in networks and define the
shortest-path distance, the basic metric on the vertex set of a connected graph.
Cycle detection determines whether an undirected graph is a forest (cycle-free) and
whether a directed graph is a DAG (directed acyclic graph). This test is critical in dependency
resolution, topological sorting, and the structure of Bayesian networks. Trees themselves
underlie decision trees, random forests, and hierarchical clustering, while
spanning trees provide the minimal connected substructure of a graph, the starting point
for Kruskal's and Prim's algorithms in network design.
Example: Cycle & Induced Subgraph
Consider the following graph:
Its vertex set and edge set are as follows:
\[
V = \{a, b, c, d, e\}, \quad E = \{ab, ac, bc, be, cd, de\}.
\]
If we delete the vertex \(a\), and remove all edges incident to the vertex \(a\), we obtain a subgraph
\(G' = (V', E')\) such that
\[
V' = \{b, c, d, e\}, \quad E' = \{bc, be, cd, de\}.
\]
Since \(G' = G[\{b,c,d,e\}]\) includes all edges of \(G\) with both endpoints in \(\{b,c,d,e\}\), it is an
induced subgraph. Moreover, \(G'\) is itself a 4-cycle \(C_4\).
On the other hand, we can see the 5-cycle in \(G\), namely \(a \to c \to d \to e \to b \to a\). This is
also a subgraph of \(G\) but not an induced subgraph. Let this subgraph be
\(G'' = (V'', E'')\) such that
\[
V'' = \{a, b, c, d, e\}, \quad E'' = \{ab, ac, be, cd, de\}.
\]
In this case, we removed the edge \(bc\) from \(G\). This does not meet the definition of
an induced subgraph.
