Introduction
Graph theory is a core area of discrete mathematics that studies graphs - mathematical
structures consisting of vertices and the edges that connect them. At its heart, a graph captures the idea of
relationship: whenever objects are linked by some pairwise connection, a graph provides the natural abstraction.
This simple idea turns out to be extraordinarily powerful.
On the theoretical side, graph theory supplies rigorous frameworks for understanding connectivity, cycles, network flows,
and structural decomposition, offering deep insight into the organization of complex systems. On the practical side, graphs
model relationships in social networks, optimize routing and logistics, drive recommendation engines, and form the backbone
of modern graph neural networks and knowledge graphs in machine learning.
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; a graph has 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, pointing 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, indicating how many parallel edges exist between two
vertices. (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.)
We next turn to the local structure around each vertex - the concept of adjacency and neighborhoods.
Neighbors
The notion of adjacency — which vertices are directly joined by an edge — is the most basic local property of a graph.
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 this 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\), so edges with both endpoints in \(A \cap B\) are 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 — a quantity 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 turns out to be
one of the most informative local invariants, and leads immediately to a fundamental identity — the Handshaking Lemma —
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\)
— a property we will revisit when we discuss isomorphism invariants.
The minimum degree and maximum degree of \(G\) are denoted respectively by
\[
\delta(G) = \min_{x \in V} \deg(x), \qquad \Delta(G) = \max_{x \in V} \deg(x).
\]
The average degree of \(G\), 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 the spectral theory of
graphs.
Proposition: Handshaking Lemma
For any graph \(G = (V, E)\),
\[
\sum_{x \in V} \deg(x) = 2|E|.
\]
Proof:
We count incidences — pairs \((x, e) \in V \times E\) with \(x \in e\) — in two ways.
For each vertex \(x \in V\), the number of edges incident to \(x\) is, by definition, \(\deg(x)\);
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|. \qquad \blacksquare
\]
Extension to Multigraphs
The Handshaking Lemma extends to multigraphs (and to graphs with loops) without modification,
provided each loop at a vertex \(v\) is counted as contributing \(2\) to \(\deg(v)\). Under this
convention the proof above goes through unchanged: a loop at \(v\) is incident to \(v\) twice,
and each parallel edge between \(u\) and \(v\) contributes one incidence to each of its endpoints.
This generality is occasionally useful — for instance, when modelling road networks with
multiple direct connections, or in classical formulations of Eulerian circuits where parallel
edges arise naturally (Königsberg's seven bridges being the historical prototype).
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 density and will reappear when we study
the graph Laplacian.
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 side is even and the first term on the right is even, so \(|V_{\mathrm{odd}}|\) must
be even as well. \(\blacksquare\)
This innocent-looking corollary has surprisingly broad consequences: it underpins parity arguments
throughout graph theory, including the existence criteria for Eulerian circuits that we will encounter
in the next page.
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\), with \(D_{ii} = \deg(v_i)\), is a building block of both the
graph Laplacian \(L = D - A\) and its normalized variants used in
spectral clustering. In Graph Neural Networks (GNNs),
the degree appears explicitly in the normalization factor \(D^{-1/2}AD^{-1/2}\) that prevents high-degree "hub" nodes from dominating the
message-passing aggregation. Even the simple degree sequence of a graph can serve as a powerful feature for graph classification tasks.
Degree is an 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" if we can relabel
the vertices of one to obtain the other, 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 isomorphism from a graph
\(G\) to itself — that is, a bijection \(\varphi: V(G) \to V(G)\) preserving edges and non-edges
— is called an automorphism of \(G\).
Note that the condition is a biconditional (\(\iff\)): \(\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" — having 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. Invariants are
the primary tool for proving that two graphs are not isomorphic: if any invariant differs,
the graphs cannot be isomorphic.
Isomorphism captures when two graphs are "the same." We now turn to the complementary notion:
how to identify and analyze the parts of a single graph — its subgraphs.
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'), \qquad 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 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 (e.g., assigning jobs to applicants) and are
characterized by the absence of odd-length cycles — see the
characterization theorem
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 non-adjacent 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\) whose both 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 \(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 non-adjacent vertices \(x, y \in V(G)\).
Subgraphs describe the "parts" of a graph. We now turn to the structures that describe
how to traverse a graph - paths and cycles.
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 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 — called the connected components of \(G\) — number exactly one.
The "equivalent" formulation requires a brief check: reflexivity is the trivial path \(x = x\) of
length \(0\); 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). 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; an acyclic 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
basic edge-count lower bound for connected graphs.
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;
say \(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, the vertices of that component would be unreachable from the rest of \(G\)
after removing \(v\), contradicting connectivity of \(G\). Hence \(\deg_G(v) \geq c\). Applying
the induction hypothesis to each \(H_i\) (each of which is connected by definition), we obtain
\(|E(H_i)| \geq n_i - 1\). Summing,
\[
|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. \qquad \blacksquare
\]
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) ⟹ (2) ⟹ (3) ⟹ (4) ⟹ (1).
(1) ⟹ (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\); but in our simple-graph
setting there is at most one such edge, forcing \(P_1 = P_2\) at this step and 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 — that
is, it is a cycle. This
contradicts acyclicity.
(2) ⟹ (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\); its 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 satisfying (2)
(uniqueness of paths is preserved under deletion of a degree-\(1\) vertex). By induction
\(|E(T')| = n - 2\), hence \(|E(T)| = n - 1\).
(3) ⟹ (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) ⟹ (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 — that is, each \(T_i\) is itself a tree on \(n_i\)
vertices. By the already-proved chain (1) ⟹ (2) ⟹ (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.
\(\blacksquare\)
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 will study trees in greater depth in future pages, including
their role in Eulerian and Hamiltonian theory
and spanning tree algorithms.
Theorem: Bipartiteness via Odd Cycles
A graph \(G\) is bipartite if
and only if it contains no cycle of odd length.
Proof:
(⟹) 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. To return
to \(x_0 \in U\) after \(k\) steps, we need an even number of crossings, so \(k\) is even.
(⟸) 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, i.e., no edge has both endpoints in the same part.
Suppose otherwise: 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. If
the walk has no internal vertex repetition, it is itself a cycle, and odd length makes it an
odd cycle. Otherwise, locate the first internal repetition \(w_i = w_j\) with \(i < j\);
splitting at this repetition yields two strictly shorter closed walks — the inner segment
\(w_i, w_{i+1}, \ldots, w_j\) of length \(j - i\), and the outer segment
\(w_0, \ldots, w_i, w_{j+1}, \ldots, w_L\) of 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. \(\blacksquare\)
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 for parity violations on
back-edges — an \(O(|V| + |E|)\) procedure. The odd-cycle obstruction will reappear when we study
Eulerian circuits, planarity, and the spectral theory of graphs.
Paths, Cycles, and Trees in CS and ML
These three structures are foundation of algorithmic graph theory. Shortest paths
(Dijkstra's algorithm, Bellman-Ford) power routing in networks and are the foundation of
graph distance metrics used in node embedding methods like DeepWalk.
Cycle detection determines whether an undirected graph is a forest (cycle-free)
and whether a directed graph is a DAG (directed acyclic graph),
which 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\). (Say, \(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 just removed an edge \(bc\) from \(G\). This does not meet the definition of the induced
subgraph.
