Graph Theory
Overview
Graphs. A graph is a pair $G = (V, E)$ where $V$ is a finite set of vertices and $E$ is a set of edges, each being a 2-element subset of $V$. Graphs model pairwise relations: road networks, social connections, dependency structures. The central questions are structural: when is a graph connected? When does it contain a cycle? How are vertices and edges constrained by global properties?
Trees. A tree is a connected acyclic graph. Trees are the minimally connected graphs: removing any edge disconnects them, and adding any edge creates a cycle. They admit several equivalent characterizations, all equivalent to having exactly $|V|-1$ edges. Every connected graph contains a spanning tree, a subgraph that is a tree on all vertices.
Eulerian circuits. An Eulerian circuit is a closed trail using every edge exactly once. Euler's theorem gives a complete and simple answer: a connected graph has one if and only if every vertex has even degree. If the trail is allowed to be open, exactly two odd-degree vertices are permitted, and they become its endpoints.
Hamiltonicity. A Hamiltonian cycle visits every vertex exactly once, where an Eulerian circuit uses every edge once. No simple degree condition characterizes which graphs have one. There are useful sufficient conditions: it is enough that every vertex have degree at least $n/2$ (Dirac), or more generally that every two non-adjacent vertices have degree sum at least $n$ (Ore).
Planarity. A graph is planar if it can be drawn in the plane without edge crossings. Euler's formula $V - E + F = 2$ relates vertices, edges, and faces of any connected plane graph. This formula implies strong constraints: a simple planar graph satisfies $E \leq 3V - 6$, which immediately shows that $K_5$ is non-planar, while the sharper bound $E \leq 2V - 4$ for bipartite planar graphs rules out $K_{3,3}$. Kuratowski's theorem states these are the only obstructions, up to subdivision.
Coloring. A proper $k$-coloring assigns one of $k$ colors to each vertex so that adjacent vertices receive distinct colors. The chromatic number $\chi(G)$ is the smallest such $k$. It satisfies $\chi(G) \geq \omega(G)$ (clique lower bound) and $\chi(G) \leq \Delta(G) + 1$ (greedy upper bound). The five-color theorem states that every planar graph satisfies $\chi(G) \leq 5$, proved via Kempe chains. The four-color theorem ($\chi \leq 4$ for planar graphs) is true but requires a computer-assisted proof. For interval graphs (vertices are intervals on a line, edges mark overlaps) the chromatic number equals the clique number, which models assigning a scarce resource to requests that conflict when they overlap.
Matchings. A matching in a graph is a set of pairwise non-adjacent edges. Hall's marriage theorem characterizes exactly when a bipartite graph has a matching that covers one side: every subset $S$ of that side must have at least $|S|$ neighbors. This combinatorial condition has a clean inductive proof and powerful corollaries, such as the existence of perfect matchings in regular bipartite graphs.
Course
Graphs and basic notions
Definition (Graph). A simple undirected graph is a pair $G = (V, E)$ where $V$ is a finite nonempty set of vertices and $E \subseteq \binom{V}{2}$ is a set of edges, each being a 2-element subset of $V$. We write $n = |V|$ and $m = |E|$. Two vertices $u, v$ are adjacent (or neighbors) if $\{u,v\} \in E$. The neighborhood of $v$ is $N(v) = \{u \in V : \{u,v\} \in E\}$. For $S \subseteq V$, we write $N(S) = \bigcup_{v \in S} N(v) \setminus S$.
Definition (Degree). The degree of a vertex $v$ is $\deg(v) = |N(v)|$, the number of edges incident to $v$. The minimum degree and maximum degree of $G$ are $\delta(G) = \min_{v \in V} \deg(v)$ and $\Delta(G) = \max_{v \in V} \deg(v)$. A graph is $k$-regular if every vertex has degree $k$.
Proposition (Handshaking lemma). For any graph $G = (V, E)$, $\displaystyle\sum_{v \in V} \deg(v) = 2|E|$.
Proof.
Count the pairs $(v, e)$ with $v \in e$. Each edge $e = \{u,v\}$ contributes exactly 2 such pairs (one for $u$, one for $v$), giving $2|E|$ total. Each vertex $v$ contributes $\deg(v)$ such pairs. Thus $\sum_{v \in V} \deg(v) = 2|E|$.Corollary. In any graph, the number of vertices of odd degree is even.
Proof.
The sum $\sum_{v} \deg(v) = 2|E|$ is even. The contribution of even-degree vertices is even, so the contribution of odd-degree vertices is also even. Since each such vertex contributes an odd number, their count must be even.Definition (Subgraph). A subgraph of $G = (V,E)$ is a graph $H = (V', E')$ with $V' \subseteq V$ and $E' \subseteq E \cap \binom{V'}{2}$. The induced subgraph $G[S]$ on $S \subseteq V$ has vertex set $S$ and all edges of $G$ with both endpoints in $S$: $G[S] = (S, E \cap \binom{S}{2})$. A spanning subgraph has $V' = V$.
Definition (Walk, trail, path, cycle). A walk of length $k$ in $G$ is a sequence of vertices $v_0, v_1, \ldots, v_k$ with $\{v_i, v_{i+1}\} \in E$ for all $i$. A trail is a walk with no repeated edge. A path is a walk with no repeated vertex. A cycle is a closed walk $v_0, v_1, \ldots, v_k = v_0$ with $k \geq 3$, no repeated vertex except $v_0 = v_k$, and no repeated edge. The length of a path or cycle is its number of edges.
Definition (Connectivity). Two vertices $u, v$ are connected if there exists a path from $u$ to $v$. Being connected is an equivalence relation on $V$; the equivalence classes are the connected components of $G$. The graph $G$ is connected if it has exactly one connected component, i.e., every pair of vertices is connected. An edge $e$ is a bridge if $G - e$ (the graph with $e$ removed) has more connected components than $G$.
Definition (Standard graphs). The complete graph $K_n$ has vertex set $[n] = \{1,\ldots,n\}$ and all $\binom{n}{2}$ possible edges. The path graph $P_n$ has vertices $1, \ldots, n$ and edges $\{i, i+1\}$ for $1 \leq i \leq n-1$. The cycle graph $C_n$ ($n \geq 3$) has vertices $1, \ldots, n$ and edges $\{i, i+1\}$ for $1 \leq i \leq n-1$ plus $\{n, 1\}$. A bipartite graph is a graph whose vertex set can be partitioned into two sets $A$ and $B$ such that every edge has one endpoint in $A$ and one in $B$. The complete bipartite graph $K_{p,q}$ has parts $A$ of size $p$, $B$ of size $q$, and all $pq$ edges between $A$ and $B$.
Proposition (Bipartite characterization). A graph $G$ is bipartite if and only if it contains no cycle of odd length.
Proof.
$(\Rightarrow)$ Let $G$ be bipartite with parts $A$ and $B$. Any cycle $v_0, v_1, \ldots, v_k = v_0$ must alternate between parts. Vertices at even indices belong to one part, odd indices to the other. Since $v_0$ and $v_k$ are the same vertex, $k$ must be even. $(\Leftarrow)$ Assume $G$ has no odd cycle; it suffices to treat each connected component separately. Fix a component with root $r$. For each vertex $v$, let $d(v)$ denote the length of a shortest path from $r$ to $v$. Set $A = \{v : d(v) \text{ even}\}$ and $B = \{v : d(v) \text{ odd}\}$. Claim: every edge $\{u,v\}$ has one endpoint in $A$ and one in $B$. Suppose for contradiction that $u, v \in A$ (both have even distance from $r$). Then there exist paths of even length from $r$ to $u$ and from $r$ to $v$. Adding the edge $\{u,v\}$ creates a cycle of odd length (even $+$ 1 $+$ even $=$ odd), contradicting our assumption. The case $u, v \in B$ is identical. Thus $(A, B)$ is a bipartition and $G$ is bipartite.Trees
Definition (Forest, tree, leaf). A forest is an acyclic graph. A tree is a connected forest, i.e., a connected acyclic graph. A leaf is a vertex of degree $1$.
Proposition (Leaf lemma). Every tree with at least $2$ vertices has at least one leaf.
Proof.
Let $T$ be a tree with at least $2$ vertices, and let $v_0, v_1, \ldots, v_k$ be a longest path in $T$. Since $|V| \geq 2$, this path has length $k \geq 1$. We claim $v_k$ is a leaf. The vertex $v_k$ has at least one neighbor, namely $v_{k-1}$. Suppose $v_k$ has another neighbor $u \neq v_{k-1}$. Since $T$ is acyclic, $u$ is not any of $v_0, \ldots, v_{k-1}$ (otherwise $v_0, \ldots, v_i, v_k$ would be a shorter walk forming a cycle). But then $v_0, v_1, \ldots, v_k, u$ is a path of length $k+1$, contradicting maximality. So $\deg(v_k) = 1$.Proposition (Edge count in forests). A forest with $n$ vertices and $c$ connected components has exactly $n - c$ edges.
Proof.
By induction on $m = |E|$. If $m = 0$: all vertices are isolated, $c = n$, and $m = 0 = n - n$. If $m \geq 1$: pick any edge $e$. Since the forest is acyclic, $e$ is a bridge: removing it splits a component into two (if $e$ were not a bridge, there would be a path avoiding $e$ between its endpoints, forming a cycle with $e$). So $G - e$ has $n$ vertices, $m - 1$ edges, and $c + 1$ components. By induction, $m - 1 = n - (c+1)$, so $m = n - c$.Theorem (Characterizations of trees). Let $G$ be a graph with $n$ vertices. The following are equivalent:
(1) $G$ is connected and acyclic (a tree).
(2) $G$ is connected and has $n-1$ edges.
(3) $G$ is acyclic and has $n-1$ edges.
(4) Any two vertices of $G$ are connected by a unique path.
Proof.
$(1) \Rightarrow (2)$. By the forest edge count proposition with $c = 1$ (connected), $m = n - 1$. $(2) \Rightarrow (1)$. Suppose $G$ is connected with $n-1$ edges. If $G$ had a cycle $C$, remove an edge $e$ from $C$: the graph $G - e$ is still connected (the cycle provides an alternate path). Continue removing edges from cycles until no cycle remains: we obtain a connected acyclic spanning subgraph, which is a tree. By $(1) \Rightarrow (2)$, this tree has $n-1$ edges. But we removed at least one edge, so $G$ had at least $n$ edges, a contradiction. $(1) \Rightarrow (3)$. By the forest edge count with $c = 1$, $m = n - 1$. $(3) \Rightarrow (1)$. Suppose $G$ is acyclic with $n-1$ edges. The forest edge count gives $n - 1 = n - c$, so $c = 1$: $G$ is connected. $(1) \Leftrightarrow (4)$. At least one path exists between any two vertices (connectivity). If two paths $P_1, P_2$ connected $u$ to $v$, let $w$ be the first vertex where they diverge and $x$ the first vertex after $w$ where they meet again; the portions of $P_1$ and $P_2$ from $w$ to $x$ form a cycle, contradicting acyclicity.Definition (Spanning tree). A spanning tree of a graph $G = (V, E)$ is a spanning subgraph of $G$ that is a tree, i.e., a subgraph $(V, T)$ with $T \subseteq E$ that is connected and acyclic.
Theorem (Existence of spanning trees). Every connected graph has a spanning tree.
Proof.
Let $G$ be connected. Among all connected spanning subgraphs of $G$, let $H = (V, T)$ be one with a minimum number of edges. We claim $H$ is a tree, i.e., acyclic. Suppose $H$ contains a cycle $C$. Remove any edge $e \in C$: the graph $H - e$ is still connected (any path that used $e$ can be rerouted along the rest of $C$). This contradicts the minimality of $H$. So $H$ is acyclic, hence a tree.Eulerian graphs
Definition (Eulerian circuit and path). An Eulerian circuit in a graph $G$ is a closed trail that uses every edge of $G$ exactly once. An Eulerian path is a trail (not necessarily closed) that uses every edge of $G$ exactly once. A graph admitting an Eulerian circuit is called Eulerian.
Theorem (Euler, 1736). A connected graph $G$ has an Eulerian circuit if and only if every vertex has even degree.
Proof.
$(\Rightarrow)$ In an Eulerian circuit, each time the circuit passes through a vertex $v$, it uses one incoming and one outgoing edge. Since every edge is used exactly once, $\deg(v)$ equals twice the number of times the circuit passes through $v$, which is even. $(\Leftarrow)$ Suppose all degrees are even. We proceed by strong induction on $m = |E|$. If $m = 0$: the empty trail is an Eulerian circuit. If $m \geq 1$: since $G$ is connected with all degrees $\geq 2$ (they are even and nonzero), start at any vertex $v_0$ and greedily extend a trail, never revisiting an edge. The trail must eventually return to $v_0$: at each intermediate visit to a vertex $w \neq v_0$, we used one edge to arrive and can always depart (the degree at $w$ is even, so the number of unused edges incident to $w$ remains even and positive as long as we have not used all of them). Let $C$ be the closed trail obtained. If $C$ uses all edges, we are done. Otherwise, since $G$ is connected, some vertex $u$ of $C$ has unused incident edges. The unused edges form a subgraph $G'$ in which every vertex still has even degree (a subset of the edges of $G$, each removing 0 or 2 from a vertex's available degree... more precisely, remove the edges of $C$ from $G$; each vertex loses an even number of edges since $C$ visits it an even number of times, as its degree in $C$ is even). Each connected component of $G'$ that contains a vertex of $C$ has all-even degrees and strictly fewer edges than $G$; by induction, it has an Eulerian circuit $C'$ starting at $u$. Splice $C'$ into $C$ at $u$ to get a longer closed trail. Repeat until all edges are used.Corollary (Eulerian path). A connected graph $G$ has an Eulerian path (but not an Eulerian circuit) if and only if it has exactly two vertices of odd degree. In that case, every Eulerian path starts at one odd-degree vertex and ends at the other.
Proof.
$(\Rightarrow)$ An Eulerian path from $u$ to $v$ ($u \neq v$) traverses each edge once. Each vertex $w \notin \{u,v\}$ has even degree (enter and exit equally). The vertex $u$ has one more exit than entry, and $v$ one more entry than exit, so both have odd degree. By the handshaking corollary, the number of odd-degree vertices is even, so there are exactly two. $(\Leftarrow)$ Let $u$ and $v$ be the two odd-degree vertices. Add a new edge $e = \{u,v\}$ to get $G'$. In $G'$, all degrees are even and $G'$ is connected, so by Euler's theorem $G'$ has an Eulerian circuit. This circuit uses $e$; removing $e$ from the circuit gives an Eulerian path from $u$ to $v$ in $G$.Hamiltonian graphs
Definition (Hamiltonian path and cycle). A Hamiltonian path in $G$ is a path that visits every vertex exactly once. A Hamiltonian cycle is a cycle that visits every vertex exactly once. A graph is Hamiltonian if it has a Hamiltonian cycle. Where an Eulerian circuit uses every edge once, a Hamiltonian cycle uses every vertex once.
Remark. Unlike Euler's theorem, no simple characterization of Hamiltonian graphs in terms of local conditions such as degrees is known. The two results below give only sufficient conditions: they guarantee a Hamiltonian cycle when the graph has enough edges, but many Hamiltonian graphs fail them.
Theorem (Ore, 1960). Let $G$ be a simple graph with $n \geq 3$ vertices. If $\deg(u) + \deg(v) \geq n$ for every pair of non-adjacent vertices $u, v$, then $G$ is Hamiltonian.
Proof.
Suppose, for contradiction, that some graph satisfies the hypothesis but is not Hamiltonian. Adding an edge only increases degrees, so the hypothesis is preserved under adding edges. Starting from $G$ and adding missing edges one at a time as long as the graph stays non-Hamiltonian, we reach a graph $H$ on the same $n$ vertices that is non-Hamiltonian, satisfies Ore's condition, and is maximal with this property: adding any missing edge creates a Hamiltonian cycle. $H$ is not the complete graph $K_n$, since $K_n$ is Hamiltonian for $n \geq 3$. So $H$ has two non-adjacent vertices $u$ and $v$. By maximality, $H + \{u,v\}$ has a Hamiltonian cycle, and that cycle must use the new edge $\{u,v\}$. Removing $\{u,v\}$ leaves a Hamiltonian path from $u$ to $v$ in $H$, which we write $x_1, x_2, \ldots, x_n$ with $x_1 = u$ and $x_n = v$, covering all vertices. Consider the two index sets $S = \{ i : 1 \leq i \leq n-1 \text{ and } \{u, x_{i+1}\} \in E(H) \}$ and $T = \{ i : 1 \leq i \leq n-1 \text{ and } \{v, x_i\} \in E(H) \}$. Each neighbor of $u = x_1$ is some $x_{i+1}$ with $i \in S$, so $|S| = \deg(u)$. Each neighbor of $v = x_n$ is some $x_i$ with $i \in T$, so $|T| = \deg(v)$. Both $S$ and $T$ are subsets of $\{1, \ldots, n-1\}$, a set of size $n-1$. Since $\deg(u) + \deg(v) \geq n$, we have $|S| + |T| \geq n > n-1$, so $S$ and $T$ cannot be disjoint: there is an index $i$ with $\{u, x_{i+1}\} \in E$ and $\{v, x_i\} \in E$. (Note $n-1 \notin S$, since $\{u, x_n\} = \{u,v\}$ is not an edge; so $i \leq n-2$ and the construction below is well defined.) Now form a cycle through all $n$ vertices: $x_1, x_2, \ldots, x_i, x_n, x_{n-1}, \ldots, x_{i+1}, x_1$. It follows the path from $x_1$ to $x_i$, takes the edge $\{x_i, x_n\} = \{x_i, v\}$, runs back down the path from $x_n$ to $x_{i+1}$, then takes the edge $\{x_{i+1}, x_1\} = \{x_{i+1}, u\}$ to close up. Every vertex appears exactly once, so this is a Hamiltonian cycle in $H$, contradicting that $H$ is non-Hamiltonian. Hence no such graph exists, and every graph satisfying Ore's condition is Hamiltonian.Corollary (Dirac, 1952). Let $G$ be a simple graph with $n \geq 3$ vertices. If every vertex has degree at least $n/2$, then $G$ is Hamiltonian.
Proof.
For any two non-adjacent vertices $u, v$, we have $\deg(u) + \deg(v) \geq n/2 + n/2 = n$. So Ore's condition holds, and $G$ is Hamiltonian.Planar graphs
Definition (Planar graph, plane graph, faces). A graph $G$ is planar if it can be drawn in the plane $\mathbb{R}^2$ with vertices as distinct points and edges as Jordan arcs between their endpoints, such that no two edges cross. Such a drawing is a planar embedding. A graph together with a fixed planar embedding is a plane graph. A planar embedding divides the plane into connected regions called faces. Exactly one face is unbounded, the outer face. We write $F$ for the number of faces.
Theorem (Euler's formula). For any connected plane graph with $V$ vertices, $E$ edges, and $F$ faces, $V - E + F = 2$.
Proof.
By induction on $E$. Let $T$ be a spanning tree of $G$ (which exists since $G$ is connected). We build $G$ by starting from $T$ and adding edges one by one. Base case: $G = T$ is a tree with $V$ vertices and $V - 1$ edges. A tree drawn in the plane has only one face (the outer face): since the tree is acyclic, no edge encloses a region. So $V - (V-1) + 1 = 2$. ✓ Inductive step: Suppose $G$ has $E \geq V$ edges (so $G$ is not a tree and has cycles). Remove any edge $e$ that lies on a cycle. The graph $G - e$ is still connected (the cycle provides an alternate path) and has $V$ vertices, $E - 1$ edges, and $F - 1$ faces: the edge $e$ was shared between two distinct faces (since $e$ is on a cycle, both sides of $e$ are in the interior of a region bounded by a closed walk), and removing $e$ merges them into one face. By induction, $V - (E-1) + (F-1) = 2$, so $V - E + F = 2$.Corollary. Every simple connected planar graph with $V \geq 3$ vertices satisfies $E \leq 3V - 6$.
Proof.
In any plane graph, each face is bounded by at least $3$ edges (since the graph is simple, there are no self-loops or multi-edges). Each edge borders at most $2$ faces. Therefore $3F \leq 2E$. Substituting into Euler's formula $F = 2 - V + E$: $3(2 - V + E) \leq 2E$, giving $6 - 3V + 3E \leq 2E$, i.e., $E \leq 3V - 6$.Corollary. $K_5$ is not planar.
Proof.
$K_5$ has $V = 5$ and $E = 10$. If it were planar, the previous corollary would give $10 \leq 3(5) - 6 = 9$, a contradiction.Corollary. Every simple connected bipartite planar graph with $V \geq 3$ vertices satisfies $E \leq 2V - 4$.
Proof.
In a bipartite graph, every cycle has even length (by the bipartite characterization), so every face is bounded by at least $4$ edges. Therefore $4F \leq 2E$, i.e., $2F \leq E$. Substituting $F = 2 - V + E$: $2(2 - V + E) \leq E$, giving $4 - 2V + 2E \leq E$, i.e., $E \leq 2V - 4$.Corollary. $K_{3,3}$ is not planar.
Proof.
$K_{3,3}$ is bipartite with $V = 6$ and $E = 9$. If it were planar, the previous corollary would give $9 \leq 2(6) - 4 = 8$, a contradiction.Graph coloring
Definition (Coloring, chromatic number). A proper $k$-coloring of a graph $G = (V,E)$ is a function $c : V \to \{1, \ldots, k\}$ such that $c(u) \neq c(v)$ for every edge $\{u,v\} \in E$. The chromatic number $\chi(G)$ is the smallest $k$ for which a proper $k$-coloring exists.
Definition (Clique, independence number). A clique in $G$ is a complete subgraph, i.e., a subset $S \subseteq V$ where every pair of vertices is adjacent. The clique number $\omega(G)$ is the size of the largest clique. An independent set is a set $S \subseteq V$ of pairwise non-adjacent vertices. The independence number $\alpha(G)$ is the size of the largest independent set.
Proposition (Lower bounds on $\chi$). For any graph $G$ with $n$ vertices, $\chi(G) \geq \omega(G)$ and $\chi(G) \geq \lceil n / \alpha(G) \rceil$.
Proof.
For $\chi(G) \geq \omega(G)$: in any clique of size $\omega(G)$, all vertices are pairwise adjacent and must therefore receive distinct colors in any proper coloring. So at least $\omega(G)$ colors are needed. For $\chi(G) \geq \lceil n / \alpha(G) \rceil$: each color class (the set of vertices receiving a given color) is an independent set, so has size at most $\alpha(G)$. With $k$ colors, at most $k \cdot \alpha(G)$ vertices can be colored. Since all $n$ vertices must be colored, $k \cdot \alpha(G) \geq n$, giving $k \geq n / \alpha(G)$.Proposition (Greedy upper bound). For any graph $G$, $\chi(G) \leq \Delta(G) + 1$.
Proof.
Order the vertices $v_1, v_2, \ldots, v_n$ arbitrarily. Color them in this order: assign to $v_i$ the smallest color in $\{1, \ldots, \Delta(G)+1\}$ not used by any previously colored neighbor of $v_i$. At step $i$, $v_i$ has at most $\Delta(G)$ neighbors, so at most $\Delta(G)$ colors are forbidden; thus a color in $\{1, \ldots, \Delta(G)+1\}$ is always available.Theorem (Five-color theorem). Every planar graph satisfies $\chi(G) \leq 5$.
Proof.
By induction on $|V|$. The base case $|V| \leq 5$ is immediate (assign a distinct color to each vertex). Existence of a low-degree vertex. Since $G$ is planar with $V \geq 6$, we have $E \leq 3V - 6$, so the average degree $2E/V \leq (6V-12)/V < 6$. Hence $G$ has a vertex $v$ with $\deg(v) \leq 5$. Inductive step. By induction, $G - v$ has a proper $5$-coloring $c$. If $\deg(v) \leq 4$, the neighbors of $v$ use at most $4$ colors, so a fifth color is available for $v$. Suppose $\deg(v) = 5$. Let $v_1, v_2, v_3, v_4, v_5$ be the neighbors of $v$ in cyclic order around $v$ in the planar embedding, with colors $c(v_i) = i$ (if the five neighbors do not use all five colors, we again have a free color for $v$, so assume they do). For $i \neq j$, let $H_{ij}$ denote the subgraph of $G - v$ induced by vertices colored $i$ or $j$. Consider $H_{13}$. If $v_1$ and $v_3$ are in different connected components of $H_{13}$, swap colors $1$ and $3$ in the component of $v_1$: now $v_1$ has color $3$ and all five neighbors of $v$ use only colors in $\{2,3,4,5\}$, so color $1$ is free for $v$. If $v_1$ and $v_3$ are in the same component of $H_{13}$, there is a path $P$ from $v_1$ to $v_3$ in $H_{13}$. In the plane, this path $P$ together with the two edges $\{v, v_1\}$ and $\{v, v_3\}$ forms a closed curve that separates $v_2$ (inside) from $v_4$ and $v_5$ (outside), or vice versa. In either case, $v_2$ and $v_4$ are separated: any path from $v_2$ to $v_4$ in $G - v$ must cross $P$, hence pass through a vertex of $H_{13}$, which uses neither color $2$ nor color $4$. Thus $v_2$ and $v_4$ lie in different connected components of $H_{24}$. Swap colors $2$ and $4$ in the component of $v_2$: now $v_2$ has color $4$, and the five neighbors of $v$ use colors in $\{1, 3, 4, 5\}$, so color $2$ is free for $v$. In all cases, $v$ can be assigned a color, completing the induction.Definition (Interval graph). Let $I_1, \ldots, I_n$ be intervals on the real line. Their interval graph has vertex set $\{1, \ldots, n\}$, with an edge $\{i, j\}$ whenever $I_i \cap I_j \neq \emptyset$. A graph is an interval graph if it arises in this way from some family of intervals.
Remark (Conflict graphs). Interval graphs model the sharing of a resource. Take requests, each active over an interval of time or space; two requests conflict exactly when their intervals overlap. A proper coloring assigns to each request one of $k$ values (a wavelength, a frequency, a time slot) so that two overlapping requests differ, and $\chi(G)$ is the least number of values that suffices.
Proposition. Every interval graph $G$ satisfies $\chi(G) = \omega(G)$.
Proof.
The inequality $\chi(G) \geq \omega(G)$ holds for every graph. We show $\chi(G) \leq \omega(G)$ for an interval graph by coloring its intervals greedily. Order the intervals by left endpoint, breaking ties arbitrarily: $I_1, I_2, \ldots, I_n$ with left endpoints $\ell_1 \leq \ell_2 \leq \cdots \leq \ell_n$. Color them in this order, giving each interval the smallest color not yet used by an earlier interval that overlaps it. Consider the step at which $I_j$ is colored. Its already-colored neighbors are the intervals $I_i$ with $i < j$ (so $\ell_i \leq \ell_j$) that meet $I_j$. Such an $I_i$ shares a point with $I_j$; since $I_i$ starts no later than $\ell_j$, that shared point is at least $\ell_j$, so $I_i$ contains the point $\ell_j$. Hence every already-colored neighbor of $I_j$ contains $\ell_j$, and so does $I_j$ itself. These intervals pairwise overlap, since they all contain $\ell_j$, so they form a clique. Its size is at most $\omega(G)$, so $I_j$ has at most $\omega(G) - 1$ already-colored neighbors, and the smallest available color is at most $\omega(G)$. The greedy coloring therefore uses at most $\omega(G)$ colors, giving $\chi(G) \leq \omega(G)$.Matchings
Definition (Matching). A matching in a graph $G = (V, E)$ is a set $M \subseteq E$ of pairwise non-adjacent edges (no two edges of $M$ share a vertex). A vertex $v$ is saturated (or matched) by $M$ if some edge of $M$ is incident to $v$. A matching is perfect if it saturates every vertex. In a bipartite graph $G = (A \cup B, E)$, a matching saturates $A$ if every vertex of $A$ is matched.
Theorem (Hall's marriage theorem). Let $G = (A \cup B, E)$ be a bipartite graph. There exists a matching saturating $A$ if and only if for every $S \subseteq A$, $|N(S)| \geq |S|$ (Hall's condition).
Proof.
$(\Rightarrow)$ If $M$ saturates $A$, then for any $S \subseteq A$, the matching $M$ provides $|S|$ distinct vertices in $N(S)$ (one for each vertex of $S$), so $|N(S)| \geq |S|$. $(\Leftarrow)$ By induction on $|A|$. If $|A| = 0$: done. If $|A| = 1$: Hall's condition gives $|N(\{a\})| \geq 1$, so $a$ has a neighbor; take that edge. Assume $|A| \geq 2$. We consider two cases. Case 1: for every proper nonempty $S \subsetneq A$, $|N(S)| \geq |S| + 1$. Pick any $a \in A$ and any neighbor $b \in N(a)$. In $G' = G - \{a, b\}$ with parts $A' = A \setminus \{a\}$ and $B' = B \setminus \{b\}$: for any $T \subseteq A'$, $N_{G'}(T) \supseteq N_G(T) \setminus \{b\}$, so $|N_{G'}(T)| \geq |N_G(T)| - 1 \geq (|T| + 1) - 1 = |T|$. By induction, $G'$ has a matching saturating $A'$; adding the edge $\{a,b\}$ saturates $A$. Case 2: there exists a proper nonempty $S \subsetneq A$ with $|N(S)| = |S|$ (a tight set). The induced subgraph $G[S \cup N(S)]$ satisfies Hall's condition by restriction; by induction, it has a matching $M_1$ saturating $S$. Consider $G'' = G[(A \setminus S) \cup (B \setminus N(S))]$. We claim Hall's condition holds in $G''$. Let $T \subseteq A \setminus S$. In $G$, $N_G(T \cup S) = N_G(T) \cup N_G(S)$, with $N_G(T) \setminus N_G(S) = N_{G''}(T)$ (since edges from $T$ going into $N_G(S)$ are absent from $G''$). Therefore $|N_G(T \cup S)| = |N_{G''}(T)| + |N_G(S)| = |N_{G''}(T)| + |S|$. By Hall's condition in $G$: $|N_G(T \cup S)| \geq |T \cup S| = |T| + |S|$. So $|N_{G''}(T)| + |S| \geq |T| + |S|$, giving $|N_{G''}(T)| \geq |T|$. By induction, $G''$ has a matching $M_2$ saturating $A \setminus S$. Since $M_1$ and $M_2$ use vertices in disjoint sets ($N(S)$ and $B \setminus N(S)$), $M_1 \cup M_2$ is a matching saturating $A$.Corollary. Every $k$-regular bipartite graph ($k \geq 1$) has a perfect matching.
Proof.
Let $G = (A \cup B, E)$ be $k$-regular. First, $|A| = |B|$: counting edges from each side, $k|A| = |E| = k|B|$. We verify Hall's condition. For any $S \subseteq A$, count edges between $S$ and $N(S)$: there are $k|S|$ edges incident to $S$, all going to $N(S)$. Each vertex in $N(S)$ has degree $k$, so $k|N(S)| \geq k|S|$, giving $|N(S)| \geq |S|$. By Hall's theorem, there is a matching saturating $A$. Since $|A| = |B|$, this matching is perfect.Exercises
Exercise. Show that in any simple graph $G$ with at least $2$ vertices, there exist two vertices with the same degree.
Proof.
Let $n = |V| \geq 2$. The degree of any vertex lies in $\{0, 1, \ldots, n-1\}$. However, the values $0$ and $n-1$ cannot both occur simultaneously: degree $n-1$ means a vertex is adjacent to all others, which forces all degrees to be $\geq 1$, contradicting degree $0$. So the $n$ degrees take values in a set of size at most $n-1$. By the pigeonhole principle, two vertices share the same degree.Exercise. Show that every tree is bipartite.
Proof.
A tree is acyclic, so in particular it contains no cycle at all, and a fortiori no odd cycle. By the bipartite characterization, the tree is bipartite.Exercise. Show that a graph $G$ is a tree if and only if there is exactly one path between every pair of vertices.
Proof.
$(\Rightarrow)$ Let $G$ be a tree. It is connected, so between any two vertices $u, v$ there is at least one path. Suppose two distinct paths $P$ and $Q$ join $u$ to $v$. Since they differ, there is a first vertex $x$ (going from $u$) after which they diverge; and since both end at $v$, they meet again, so let $y$ be the first vertex on $P$ after $x$ that also lies on $Q$. The portion of $P$ from $x$ to $y$ and the portion of $Q$ from $x$ to $y$ meet only at $x$ and $y$, so together they form a cycle, contradicting that a tree is acyclic. Hence the path is unique. $(\Leftarrow)$ Suppose there is exactly one path between every pair of vertices. In particular at least one path exists between any two vertices, so $G$ is connected. If $G$ contained a cycle, two vertices on that cycle would be joined by two distinct paths (the two arcs of the cycle), contradicting uniqueness. So $G$ is acyclic. Connected and acyclic, $G$ is a tree.Exercise. Let $G$ be a connected graph with $n$ vertices, $m$ edges, and $k$ vertices of odd degree. Show that the minimum number of trails needed to decompose the edges of $G$ is $\max(1, k/2)$.
Proof.
By the handshaking corollary, $k$ is even, so $k/2$ is an integer. Lower bound. Each trail contributes to exactly $2$ vertices (its endpoints) an odd degree increase of $1$ each (from the trail itself), or $0$ if it is closed. More precisely: in any trail, its two endpoints have odd degree within the trail (contributing $1$ each), and all internal vertices have even degree. A closed trail contributes $0$ odd-degree vertices. So $t$ trails collectively produce at most $2t$ odd-degree vertices in $G$. Since $G$ has $k$ odd-degree vertices, we need $2t \geq k$, i.e., $t \geq k/2$. Also $t \geq 1$ if $m \geq 1$. Upper bound. Add $k/2$ new edges pairing up the odd-degree vertices to obtain $G'$ where all degrees are even. By Euler's theorem, $G'$ has an Eulerian circuit. Removing the $k/2$ added edges splits the circuit into at most $k/2$ trails (each added edge removal can split a circuit into at most one more trail). If $k = 0$, one trail (the Eulerian circuit) suffices.Exercise. Show that if $G$ is bipartite with parts $A$ and $B$ of different sizes ($|A| \neq |B|$), then $G$ has no Hamiltonian cycle.
Proof.
Suppose $G$ had a Hamiltonian cycle $v_1, v_2, \ldots, v_n, v_1$. Since $G$ is bipartite, consecutive vertices lie in different parts, so the cycle alternates between $A$ and $B$. Its length $n$ is therefore even, and exactly half of its $n$ vertices lie in $A$ and half in $B$. Since a Hamiltonian cycle visits every vertex exactly once, this gives $|A| = |B| = n/2$, contradicting $|A| \neq |B|$. So $G$ has no Hamiltonian cycle.Exercise. Show that every simple planar graph has a vertex of degree at most $5$.
Proof.
If $G$ has at most $2$ vertices, every degree is at most $1$ and the claim is immediate. So assume $V \geq 3$, giving $E \leq 3V - 6$. Suppose, for contradiction, that every vertex had degree at least $6$. By the handshaking lemma, $2E = \sum_{v} \deg(v) \geq 6V$, so $E \geq 3V$. But $3V > 3V - 6 \geq E$, a contradiction. Hence some vertex has degree at most $5$.Exercise. Show that the Petersen graph (10 vertices, 15 edges, girth 5) is not planar.
Proof.
The Petersen graph is not bipartite (it has $5$-cycles), so neither $E \leq 3V - 6$ nor $E \leq 2V - 4$ settles it: both give $15 \leq 24$ and $15 \leq 16$, which hold. We use instead a refinement that accounts for the girth $g$ (length of the shortest cycle). In any plane graph with $V \geq 3$ and at least one cycle, each face is bounded by at least $g$ edges, and each edge borders at most $2$ faces. Thus $gF \leq 2E$, i.e., $F \leq 2E/g$. Substituting into Euler's formula: $2 = V - E + F \leq V - E + 2E/g$, giving $E \leq \frac{g}{g-2}(V - 2)$. The Petersen graph has $V = 10$, $E = 15$, and $g = 5$. If it were planar: $15 \leq \frac{5}{3}(10 - 2) = \frac{40}{3} \approx 13.3$, a contradiction. So the Petersen graph is not planar.Exercise. Show that if $G$ is a planar graph (not necessarily connected) with $V$ vertices, $E$ edges, $F$ faces, and $k$ connected components, then $V - E + F = 1 + k$.
Proof.
Apply Euler's formula to each connected component $G_1, \ldots, G_k$ drawn in the plane. Each component $G_i$ satisfies $V_i - E_i + F_i = 2$ by Euler's formula, where $F_i$ is the number of faces of $G_i$. However, the outer face of each component is shared with the others; summing naively over components over-counts the outer (unbounded) face: each component contributes $1$ outer face, but they all share the same outer face of the whole drawing. Thus $V - E + F = \sum_i (V_i - E_i + F_i) - (k-1) = 2k - (k-1) = k + 1$.Exercise. Determine $\chi(K_n)$, $\chi(C_n)$, and $\chi(K_{p,q})$.
Proof.
$\chi(K_n) = n$. Every pair of vertices is adjacent, so all $n$ vertices must receive distinct colors. Thus $\chi(K_n) \geq n$. The assignment $c(v_i) = i$ achieves $n$ colors. $\chi(C_n)$. If $n$ is even: $C_n$ is bipartite (it has no odd cycle), so $\chi(C_n) \leq 2$. Since $C_n$ contains edges, $\chi(C_n) \geq 2$. Thus $\chi(C_n) = 2$. If $n$ is odd: $C_n$ itself is an odd cycle, so it is not bipartite, giving $\chi(C_n) \geq 3$. Color the vertices $v_1, \ldots, v_n$ cyclically: $c(v_i) = 1$ if $i$ is odd and $i < n$, $c(v_i) = 2$ if $i$ is even, and $c(v_n) = 3$. This is a valid $3$-coloring, so $\chi(C_n) = 3$. $\chi(K_{p,q}) = 2$ for $p, q \geq 1$. $K_{p,q}$ is bipartite with parts $A$ and $B$: color $A$ with color $1$ and $B$ with color $2$. Since $p, q \geq 1$ there is an edge, so $\chi(K_{p,q}) \geq 2$.Exercise. Show that a tree has at most one perfect matching.
Proof.
By strong induction on the number of vertices $n$. If $n$ is odd, no perfect matching exists and there is nothing to prove; if $n = 0$, the empty matching is the only one. Suppose $n \geq 2$ is even. A tree with at least $2$ vertices has a leaf $\ell$, whose only neighbor is some vertex $u$. In any perfect matching, $\ell$ must be matched, and its only possible partner is $u$, so the edge $\{\ell, u\}$ belongs to every perfect matching. Deleting $\ell$ and $u$ leaves a forest $F$, and a perfect matching of the tree is exactly $\{\ell, u\}$ together with a perfect matching of $F$. Each component of $F$ is a tree on fewer than $n$ vertices, so by the induction hypothesis it has at most one perfect matching; hence $F$ has at most one, and therefore so does the tree.Exercise (Mantel's theorem). Show that any triangle-free graph on $n$ vertices has at most $n^2/4$ edges.
Proof.
Let $G$ be triangle-free. For any edge $\{u,v\} \in E$, the sets $N(u)$ and $N(v)$ are disjoint: if $w \in N(u) \cap N(v)$, then $u, v, w$ form a triangle. Since $N(u)$ and $N(v)$ are disjoint subsets of $V$, we have $\deg(u) + \deg(v) \leq n$. Sum over all edges: $\sum_{\{u,v\} \in E} (\deg(u) + \deg(v)) \leq n|E|$. The left side equals $\sum_{v \in V} \deg(v)^2$: each vertex $v$ contributes $\deg(v)$ to the degree of each of its $\deg(v)$ neighbors' edge-sums, for a total of $\deg(v)^2$. By the Cauchy-Schwarz inequality: $\sum_{v} \deg(v)^2 \geq \frac{1}{n}\left(\sum_{v} \deg(v)\right)^2 = \frac{(2|E|)^2}{n} = \frac{4|E|^2}{n}$. Combining: $\frac{4|E|^2}{n} \leq n|E|$, giving $|E| \leq \frac{n^2}{4}$.Exercise (Ramsey number $R(3,3) = 6$). Show that any 2-coloring of the edges of $K_6$ contains a monochromatic triangle. Show that there exists a 2-coloring of the edges of $K_5$ with no monochromatic triangle.