Math 4120: Graph Theory and Combinatorics

1. Basic Definitions

The Definition of a Graph

Remarks: Recall that an unordered pair is just any two-element set \(\{ u , v \}\), where \(u\ne v.\) For brevity, we often write such an edge more simply as \( uv \). In various contexts, it is common to denote an edge by the ordered pair \( (u,v) \). This leads to an alternative definition of a graph, equivalent to ours, as a relation on the vertex set \(V(G)\) that is both symmetric (meaning that \( (u,v) \) is an edge if and only if \( (v,u) \) is an edge) and irreflexive (meaning that \( (u,u) \) is never an edge.)

Example 1:

Neighborhood and Degree

For any edge \( uv \in E(G) \), the vertices \( u, v \in V(G) \) are said to be adjacent and/or neighbors in \( G \). The vertices \( u, v \) are called the ends of the edge \( uv \), and any edge is said to be incident at either of its ends.

For any vertex \( u \in V(G) \), we define its neighborhood as the set $$ \Gamma(u) = \{ v \in V(G) \mid uv \in E(G) \}. $$ The degree of \( u \) is the integer \( d(u) = \#\Gamma(u) \), which counts the number of \(u\)'s neighbors.

Our notation for neighborhood and degree suppress the dependence on the graph \(G,\) which is usually clear from the context. In cases where we must consider multiple graphs, we may instead write \(\Gamma_G\) and \(d_G.\)

If we sort the degrees of a graph's vertices in descending order, \( d(v_1) \ge \ldots \ge d(v_n) \), we obtain a sequence of nonnegative integers, written \( d(v_1) d(v_2) \cdots d(v_n) \), which is called the degree sequence of the graph.

Example 1 (cont.):

• \( \Gamma(1)=\{2,3\} \quad \quad \quad \Rightarrow \quad d(1)=2 \)
• \( \Gamma(2)=\{1,3\} \quad \quad \quad \Rightarrow \quad d(2)=2 \)
• \( \Gamma(3)=\{1,2,4,6\} \quad \Rightarrow \quad d(3)=4 \)
• \( \Gamma(4)=\{3,5,6\} \quad \quad \Rightarrow \quad d(4)=3 \)
• \( \Gamma(5)=\{4,6\} \quad \quad \quad \Rightarrow \quad d(5)=2 \)
• \( \Gamma(6)=\{3,4,5\}\quad \quad \Rightarrow \quad d(6)=3 \)

Variations on the Definition of a Graph

• Directed Graph (Digraph): Edges are ordered pairs, often denoted \( \overrightarrow{uv} \) (an edge directed from \( u\) to \( v \). Digraphs allow the possibility of loops, which are edges of the form \( \overrightarrow{uu} \). A digraph with no loops is essentially a graph if it has the property that \( \overrightarrow{uv} \) is a directed edge if and only if \( \overrightarrow{vu} \) is.
• Multigraph: The same edge can appear more than once. More formally, an (undirected) multigraph consists of a vertex set \( V(G) \), edge set \( E(G) \), and incidence function \( \psi \) that takes edges to unordered pairs of vertices: if ordered pairs are used, one obtains a directed multigraph. In addition to loops, in a multigraph it is possible to have parallel edges, meaning \( e, e' \in E(G) \) such that \( \psi (e) = \psi (e') = uv. \) A multigraph is simple if it has no loops or parallel edges.

The Handshaking Lemma

One consequence of this result is the saying that "at any party, an even number of hands are shaken."

2. Subgraphs, Isomorphism, and Connected Graphs

A graph \( G' \) is a subgraph of \( G \) if \( V(G') \subseteq V(G) \) and \( E(G') \subseteq E(G) \). We write \( G' \subset G \).

For any subset of vertices \( U \subseteq V(G) \), we may form the induced subgraph \( G[U] \) with vertex set \( U \) and edge set \( \{ uv \in E(G) \mid u,v \in U \} \). "Induced subgraph" is a stronger condition than "subgraph."

Consider the graph \( G \) shown below:

Complete Graphs and Isomorphism

Here is another image of a \(4\)-clique:

All cliques of a given size are exactly the same up to relabeling: this is formalized by the notion of graph isomorphism. Recall that a bijection between two sets is a function that is one-to-one and onto. Two graphs \( G, H \) are isomorphic if there exists a bijection of vertex sets \( \iota : V(G) \to V (H) \) that preserves adjacency: $$ uv \in E(G) \quad \Leftrightarrow \quad \iota (u) \iota (v) \in E(H).$$

It is not always obvious when two graphs are isomorphic: consider, for example, the two isomorphic graphs shown below, where we may construct the following isomorphism: $$\iota (1)= 8, \quad \iota (2) = 10, \quad \iota (3) = 9, \quad \iota (4) = 6, \quad \iota (5) = 7. $$

For the \( 5 \)-clique shown below, it turns out we cannot draw all \( 10 \) edges in the plane without crossings. Graphs which can be drawn in this way are said to be planar. Planar graphs are characterized by a theorem of Kuratowski, which we will discuss later in the course.

Paths, Cycles, and Connectivity

A path is a graph \( P \) of the form \( V(P) = \{x_0, \dots, x_l\} \) and \( E(P) = \{x_0x_1, x_1x_2, \dots, x_{l-1}x_l\} \), where all vertices \( x_i \) must be distinct. The number of edges \( l \) is the length of \( P \). A path may also be denoted by \( x_0 \dots x_l \). The vertices \( x_0, x_l \) are the ends of the path \( P \), which is also said to be a \( x_0 x_l \)-path, or a path from \( x_0 \) to \( x_l) \). The ends of a path are the two unique degree-1 vertices: any other vertices must have degree 2.

Similarly, a cycle of length \( l \) is a graph \( C \) with vertex set \( V(C) = \{ x_1, \dots, x_l\} \) and edge set \( E(C) = \{ x_1x_2, \dots, x_{l-1}x_l, x_l x_1 \}. \) All vertices in a cycle must have degree 2.

When we refer to a "path" or a "cycle" in a graph, one should think of a subgraph isomorphic to the path and cycle graphs defined above. In an \( n \)-vertex graph, a Hamiltonian path is any path of length \( n-1 \), and a Hamiltonian cycle is any cycle of length \( n \). Currently, there is no known algorithm for efficiently detecting Hamiltonian paths or cycles in a graph: this is related to the famous unsolved P vs NP problem.

A graph \( G \) is connected if it contains a \( uv \)-path for any \( u, v \in V(G) \). A maximal connected subgraph is a called a connected component. In most circumstances, if we have a graph with multiple connected components, it is better to think of the connected components separately as connected graphs.

Census of Small Graphs

A Connectivity Criterion

3. Walks, Trails, Circuits and All That

Basic Definitions

Example:

Finding paths and cycles in walks

Bipartite Graphs

Remark: The notation \(A \sqcup B\) is used when taking the union \( A \cup B \) of two sets which are disjoint, \( A \cap B = \emptyset \).

We've already encountered several examples of bipartite graphs. One of them is the "UFO graph" shown below, better known as the complete bipartite graph \( K_{2,3} \). A suitable vertex bipartition is indicated by the red and blue vertices below. Observe that every cycle in this graph has length \( 4 \). More generally, for any integers \( m,n \ge 1 \), there is a complete bipartite graph \( K_{m,n} \) on \( m+n \) vertices which can be defined as folllows: $$ V(K_{m,n})= \{ a_1, \ldots , a_m, b_1, \ldots , b_n \}, \quad E (K_{m,n} ) = \{ a_i b_j \mid a_i \in A , b_j \in B \}. $$

Eulerian Trails and Circuits

A trail in a multigraph \( G \) that visits every edge is said to be an Eulerian trail. Similarly, we define an Eulerian circuit to be a circuit which visits every edge exactly once. A graph is Eulerian if it contains an Eulerian circuit.

Eulerian circuits are named after Leonhard Euler, who solved in 1736 a famous problem known as the Seven Bridges of Königsberg. The image below shows the city of Königsberg (now Kaliningrad, Russia.) Notice there are 7 bridges separating 4 landmasses. Can we cross all 7 bridges without using the same bridge twice?

Naturally, we will model this problem by constructing a multigraph, whose four vertices correspond to the landmasses, and whose seven edges correspond to the bridges.

Hamiltonian Graphs

We have seen that Eulerian graphs have a characterization which can be checked efficiently: examine each vertex and check if it has even degree. In fact, our inductive proof of this characterization already suggests an algorithm for constructing an Eulerian circuit, given that the graph is in fact Eulerian: find a circuit, delete the edges, and recurse on some smaller connected component.

The Seven Bridges Problem that motivated our study of Eulerian graphs is superficially similar to the Traveling Salesperson Problem (TSP), which relates to Hamiltonian graphs, those graphs which contain a cycle through every vertex. Suppose a salesperson must visit \( n \) cities, labeled \( 1, 2, \dots, n \). The cost of traveling from city \( i \) to city \( j \) is given by a nonnegative number \( c (i,j) \ge 0 \). The TSP then asks: what is the minimum cost trip that visits all cities and returns back to the original city?

Recognizing Hamiltonian graphs is a special case of TSP. To see this, let \( G \) any graph on \( V(G)=\{1, \dots, n\} \). We define a set of \( \binom{n}{2} \) costs as follows: whenever \( 1 \le i < j \le n \), $$ c(i,j) = \begin{cases} 0 & \text{if } ij \in E(G) \\ 1 & \text{if } ij \notin E(G) \end{cases} $$ With this choice of costs, observe that \( G \) has a Hamiltonian cycle \( \iff \) Salesperson has a free trip.

As we have already noted, an efficient characterization of Hamiltonian graphs is currently unknown: providing one would be a major breakthrough. On the other hand, it is possible to give some sufficient conditions implying Hamiltonicity.

Note that the converse of Ore's theorem is false: there are many Hamiltonian graphs where \( d(u) + d(v) < \# V(G) \) for some non-edge \( uv \notin E(G) \). The simplest example is the cycle \( C_5 \), shown below.

Our proof of Ore's Theorem will rely on the lemma below.

In contrapositive form, Lemma 1 states that if a longest path in a connected graph \( G \) is shorter than a longest cycle, then \( G \) is Hamiltonian. Indeed, in any Hamiltonian graph \(G \) on \( n \) vertices, the longest cycle has length \( n \) and a longest path has \( n- 1 \).

Shortest Paths

Graph Distance: On a connected graph, for \( u, v \in V(G) \), \( d(u,v) \) is the length of a shortest \( uv \) path.

Finding a longest path has played a role in the proofs of several of our results so far. Unfortunately, this is yet another problem that is difficult to solve in practice. Surprisingly, it is much easier to find shortest paths in a graph \( G \). This is true even if we attach nonegative weights/costs to the edges of \(G \).

Dijkstra's Algorithm finds a shortest \( s-v \) path for some fixed \( s \in V(G) \), and all \( v \in V(G) \setminus \{s\} \). More generally, this algorithm works for graphs with cost function on edges, \( c: E(G) \to \mathbb{R}_{\ge 0} \). $$ d(u,v) = \displaystyle\min_{P: \text{ a } uv\text{-path}} \Bigg( \displaystyle\sum_{e \in P} c(e)\Bigg)$$

To illustrate Dijkstra's algorithm, let us consider an example of an undirected graph \( G \), with numeric labels indicating the cost \( c(u,v) \) on each edge \( uv \in E(G) \):

First iteration

\( V = \{ s \} \)
Total costs of cut edges: sa (cost 6), sb (cost 2).

Second iteration

\( V = \{ s , b\} \)
Total costs of cut edges: sa (cost 6), bd (cost 2+2=4 ), be (cost 2+5=7).

Third iteration

\( V = \{ s , b, d\} \)
Total costs of cut edges: sa (cost 6), da (cost 1+4=5), dc (cost 4+4=8), de (cost 4+2=6), be (cost 2+5=7)

Fourth iteration

\( V = \{ s , b, d, a\} \)
Total costs of cut edges: ac (cost 5+2=7), dc (cost 4+4=8), de (cost 4+2=6), be (cost 2+5=7)

Fifth iteration

\( V = \{ s , b, d, a, e\} \)
Total costs of cut edges: ac (cost 5+2=7), ec (cost 6+4=10), dc (cost 4+4=8)

Upon termination, all vertices are visited, and Dijkstra's Algorithm has generated a search tree in which every vertex is labeled by its distance from the source.

4. Trees

Basic Facts and Examples

A tree is any graph satisfying the equivalent conditions of this theorem.

Minimum Spanning Trees (MST) & Kruskal's Algorithm

Problem: You work for an airline, trying to create a network connecting all cities, where each flight has a fixed nonnegative cost, such as in the example below. Your task is to minimize the total cost of all flights while ensuring all cities are connected. The solution to this problem is to run only the flights in a spanning tree.

For any graph \(G \), a subgraph \( T \subseteq G \) is a spanning tree of \( G\) if \( T \) is a tree with \( V(T) = V(G) \). The Tree Theorem of the previous section has the important corollary that any connected graph \( G \) contains a spanning tree. Indeed, the spanning trees of \( G \) are precisely its minimally-connected subgraphs.

In general, we may pose the following Minimum Spanning Tree (MST) Problem:
Input: Connected graph \( G \), cost function \( c: E(G) \to \mathbb{R} \).
Goal: Find a spanning tree \( T \subset G \) minimizing \( \sum_{e \in E(T)} c(e) \).

Remark: In practice, costs are usually nonnegative. However, unlike our solution for shortest-paths using Dikstra's algorithm, we will be able to find a minimum spanning tree even without this assumption.

We have already encountered spanning trees in our study of Dikstra's algorithm. However, it is important to note that Dijkstra's algorithm does not solve the MST problem. To see this, consider the example shown below. Check for yourself that there are multiple solutions to the MST problem attaining the minimum cost \( 6 \), yet Dijkstra's algorithm will always generate a spanning tree of cost \( 7\), regardless of the source vertex.

Kruskal's algorithm, given below, is similar to Dijktra's algorithm in the sense that it is a "greedy algorithm", which makes a locally optimal choice during each step. But, unlike Dijkstra's algorithm, Kruskal's algorithm yields a globally optimal solution to the MST problem.

Application to the Metric TSP

This instance of metric TSP has a unique solution given by the Hamiltonian cycle \(C_* = wyxzw\), with cost of \(c(C_*) = 1 + 1 + \sqrt{2} + \sqrt{2} = 2 + 2\sqrt{2} \approx 4.828\). This can be verified by comparing the cost of \( C_* \) to the other two Hamiltonian cycles: for example, the cycle \( C = wxzyw \), which has total cost \( c(C) = 2 + \sqrt{2} + 1 + 1 \approx 5.414. \) The cycle \( C \) was constructed using the heuristic procedure below.

Cayley's Formula

How many trees are there on \( n \) vertices? The question as we have posed it is vague: one must distinguish between labeled and unlabeled trees. In general, the number of unlabeled objects is less than the number of labeled objects, but producing formulas for the number of labeled objects is much easier. For example, the number of unlabeled graphs on \( n \) vertices equals \( 2^{\binom{n}{2}} \). For \( n = 4 \), this tells us there are \( 64 \) labeled graphs. However, many of these graphs are isomorphic; the number of unlabeled \( 4 \)-vertex graphs is just \( 11 \).

Returning to the problem of counting trees, let us start by considering the case of \( n = 4 \). First, we determine the number of unlabeled trees. We know that \( 4 \)-vertex tree must have at least two leaves. Notice that the number of leaves cannot equal \( 4 \), as the sum over all vertex degrees must equal \( 6 \). If the number of leaves is exactly \( 2 \), the only possibility up to isomorphism is a path of length \( 3 \). If the number of leaves is exactly \( 3 \), the only possibility is a star.

Since there are just two isomorphism classes of \( 4 \)-vertex trees, it remains to count the number of ways in which we can assign labels from the set \( \{ 1,2,3,4 \} \) to the vertices. For the star, a labelling is determined by the choice of the degree-\( 3 \) vertex; thus, there are \( 4 \) labeled stars. For the paths, a labelling is determined by a sequential ordering of the labels; although there are \( 4! = 24 \) such orderings, reversing the order produces the same labeled tree, so there are exactly \( 12 \) labeled paths. We show all \( 16 \) labeled trees below.

Our count of \( 16 = 4^{4-2} \) labeled \( 4 \)-vertex trees produced above is an instance of the following result.

In this section, we will describe a bijective proof of Cayley's theorem, which establishes a one-to-one correspondence between the set of labeled trees on \( n \) vertices and the set of sequences of length \( n-2 \) with entries from \( \{1, 2, \dots, n\} \). Such a sequence will called a Prüfer sequence. For ease of notation, we write \( [n] = \{ 1,\ldots , n \} \) and \( [n]^{(n-2)} \) for the set of all such sequences. (In the next section, we will see a different proof of Cayley's theorem based on matrix algebra.)

Both the bijective correspondence described above and its inverse can both be described by simple algorithms. We we refer to these algorithms below as Prüfer encoding and the Prüfer decoding, respectively.

Prüfer Encoding (Tree to Sequence)
Let \( T \) be a tree with vertices labeled \( \{1, 2, \dots, n\} \). We construct a sequence \( S \) of length \( n-2 \) as follows:

1. Find the leaf (vertex of degree 1) with the smallest label.
2. Record the label of its unique neighbor as the next element in the sequence \( S \).
3. Delete the leaf and the edge connecting it to its neighbor from \( T \).
4. Repeat this process until exactly two vertices remain in the tree.

Let's find the Prüfer sequence \( P(T) \) for the 7-vertex tree \( T \) shown below. Because there are \( n = 7 \) vertices, our final sequence will have exactly \( 7 - 2 = 5 \) elements.

We repeatedly find the leaf (degree-1 vertex) with the smallest label, record its unique neighbor, and then remove the leaf from the graph:

• Step 1: The initial leaves are {2, 3, 5, 7}. The smallest is 2. Its neighbor is 1. We record \( 1 \) and delete vertex 2.
  Sequence so far: (1)
• Step 2: The remaining leaves are {3, 5, 7}. The smallest is 3. Its neighbor is 4. We record \( 4 \) and delete vertex 3.
  Sequence so far: (1, 4)
• Step 3: The remaining leaves are {5, 7}. The smallest is 5. Its neighbor is 4. We record \( 4 \) and delete vertex 5. Notice that deleting 5 turns vertex 4 into a new leaf!
  Sequence so far: (1, 4, 4)
• Step 4: The current leaves are {4, 7}. The smallest is 4. Its neighbor is 6. We record \( 6 \) and delete vertex 4. Now vertex 6 becomes a leaf.
  Sequence so far: (1, 4, 4, 6)
• Step 5: The current leaves are {6, 7}. The smallest is 6. Its neighbor is 1. We record \( 1 \) and delete vertex 6.
  Sequence so far: (1, 4, 4, 6, 1)

Exactly two vertices remain ({1, 7}), so the algorithm terminates. The final Prüfer sequence for this tree is \( S = (1, 4, 4, 6, 1) \). Notice that the degree of any vertex in the tree is exactly one more than the number of times it appears in the sequence (e.g., vertex 4 appears twice in the sequence and has a degree of 3 in the original graph).

To produce a tree from an arbitrary sequence \( S = (u_1, \ldots , u_{n-2}) \in [n]^{n-2} \), we use the following algorithm.

1. Intialize a set of labels \( L \gets [ n ] \).
2. For each element \( i=1, \ldots , n-2 \):
   • Find the smallest \( v \in L \) not appearing in the partial sequence \( (u_i, \ldots , u_{n-2}) \).
   • Add an edge between \( v \) and \( u_i \).
   • Update \( L \gets L \setminus \{ v \} \).
3. After processing the entire sequence, exactly two vertices will have a degree of 1. Add a final edge between them.

Proof of Cayley's Formula (sketch): By induction on \( n \), one may check that, for any labeled tree \( T \), if we apply the Prüfer Encoding followed by the Prüfer Decoding, then we recover \( T \). Similarly, for any sequence \( S \in [n]^{(n-2)} \), applying Prüfer Decoding and then Prüfer Encoding gives us back \( S \). Thus, these procedures define bijective inverses of each other, and the number of labelled \( n \)-vertex trees equals the cardinality of the sequence space \( [n]^{(n-2)} \), which equals \( n^{n-2} \).

Deletion-Contraction and Kirchoff's Matrix-Tree Theorem

Let \( \tau(G) \) denote the number of spanning trees of a multigraph \( G \). We define the edge contraction \( G/e \) as the multigraph obtained by deleting \( e \) and identifying its ends. Note that this operation may produce loops or parallel edges.

While this recursive formula provides an algorithm to compute the number of spanning trees, it is exponential and thus not a very efficient method in practice. We will see a better way using matrix determinants.

Let \( G \) be a multigraph with \( V(G)=\{1,2,\dots,n\} \). The adjacency matrix of \( G \) is an \( n \times n \) matrix \( A_G=(a_{ij})_{i,j=1}^n \) defined entrywise by \( a_{ij} = \# \) edges with ends \( i, j \).

The Laplacian matrix of a graph is defined entrywise by \( L_G=(l_{ij}) \), where: $$ l_{ij} = \begin{cases} \sum_{k \neq i} a_{ik} & \text{if } i=j \\ -a_{ij} & \text{otherwise} \end{cases} $$ Note that the rows and columns of the Laplacian sum to 0, and hence \( \det L_G = 0 \).

Consider a "diamond" graph \( G \) on 4 vertices with a central edge \( e \). We can observe by counting that \( \tau(G) = 8 \) (there are 4 spanning trees containing \( e \), and 4 not containing \( e \)). The Laplacian matrix \( L_G \) and the submatrix \( L_G(1) \) (obtained by deleting the first row and column) are given by: $$ L_G = \begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 2 & 0 \\ -1 & -1 & 0 & 2 \end{pmatrix}, \quad L_G(1) = \begin{pmatrix} 3 & -1 & -1 \\ -1 & 2 & 0 \\ -1 & 0 & 2 \end{pmatrix} $$ Calculating the determinant yields \( \det L_G(1) = 3(4-0) - (-1)(-2-0) + (-1)(0-(-2)) = 12 - 2 - 2 = 8 \), verifying the theorem.

First, we establish a useful lemma regarding determinants.

5. Flows, Connectivity, and Matching

Max-Flow, Min-Cut

Networks and Flows

A network is a quadruple \( N = (D, s, t, c) \), where \( D \) is a digraph, \( s, t \in V(D) \) are vertices, and \( c: E(D) \to \mathbb{R}_{\ge 0} \cup \{\infty\} \) is a nonnegative capacity function on edges. The distinguished vertices \( s \) and \( t \) are called the source and sink of \( N \), respectively.

For any \( u \in V(D) \), we define $$\Gamma^+(u) = \{ v \in V(D) \mid \overrightarrow{uv} \in E(D) \} \quad \text{(out-neighborhood)}$$ $$\Gamma^-(u) = \{ v \in V(D) \mid \overrightarrow{vu} \in E(D) \} \quad \text{(in-neighborhood)}$$

A flow on a newtwork \( N = (D, s,t,c \) is any function \( f: E(D) \to \mathbb{R}_{\ge 0} \cup \{\infty\} \) satisfying the following two conditions:

1. (capacity constraints) $$0 \le f(e) \le c(e) \text{ for all } e \in E(D) $$
2. (flow conservation constraints) $$\text{for all } u \in V(D) \setminus \{s,t\}, \quad \sum_{v \in \Gamma^+(u)} f(\overrightarrow{uv}) = \sum_{v \in \Gamma^-(u)} f(\overrightarrow{vu})$$

We define the value of a flow \( f \) as $$v(f) = \sum_{u \in \Gamma^+(s)} f(\overrightarrow{su}) - \sum_{u \in \Gamma^-(s)} f(\overrightarrow{us}).$$

Max-Flow Problem: Given a network \( N = (D, s, t, c) \), find a max flow: that is, a flow \( f: E(D) \to \mathbb{R}_{\ge 0} \cup \{\infty\} \) of maximum value (if such a flow exists).

Let \( U \subseteq V(D) \) be a set of vertices. The set of edges $$E(U, \overline{U}) = \{ \overrightarrow{uv} \in E(D) \mid u \in U, v \in \overline{U} \}$$ are the a cut edges associated with the cut.

Definition: If \( E(U, \overline{U}) \) is a cut separating \( s \) from \( t \) (\( s \in U, t \notin U \)), we define its capacity by $$\text{cap}(U) = \sum_{e \in E(U, \overline{U})} c(e).$$

Example 2

In the first iteration, we arbitrarily (and poorly) choose the augmenting path \( s uv t \). The minimum (residual) capacity along this edge is \( \varepsilon = \min(100, 1, 100) = 1 \), so we push 1 unit of flow.

Next, we choose the augmenting path \( s vut \). Now, since \( vu \) is a back-edge, we decrease the flow along \( uv \) by \( \epsilon = 1 \).

For iterations 3 through 200, the algorithm ping-pongs back and forth, alternating between these two augmenting paths. Each cycle of two iterations pushes just 2 units of total flow. Because the max flow is 200, it takes exactly 200 iterations to terminate! A more careful choice of augmenting paths, however, would allow us to finish using just 2 iterations.

Menger's Theorem and Connectivity

Graph Connectivity

Let \( G \) be a connected graph. If \( W \subseteq V(G) \) is a subset of vertices such that \( G - W \) (the subgraph induced by \( V(G) \setminus W \)) is disconnected, we say that \( W \) separates \( G \). Furthermore, if two vertices \( s \) and \( t \) belong to different connected components of \( G - W \), we say \( W \) separates \( s \) from \( t \).

For an integer \( k \ge 2 \), we say a graph is \( k \)-connected if either \( G \cong K_{k+1} \) (the complete graph on \( k+1 \) vertices) or \( \#V(G) \ge k+2 \) and no subset of \( k-1 \) vertices separates \( G \). The largest value \( k \) such that \( G \) is \( k \)-connected is called the (vertex) connectivity of \( G \), denoted \( \kappa(G) \).

Similarly, if \( W \subseteq E(G) \), we say \( G \) is \( k \)-edge-connected if \( \#E(G) \ge 2 \) and deleting any \( k-1 \) edges does not disconnect \( G \). The largest \( k \) for which \( G \) is \( k \)-edge-connected is the edge connectivity of \( G \), denoted \( \lambda(G) \).

Menger's Theorem

For \( s, t \in V(G) \), we say two \( st \)-paths are independent if they are internally vertex-disjoint; that is to say, they contain no common vertices other than the ends \( s \) and \( t \). Menger's theorem consists of two separate but related results, which provide min-max theorems related to graph connectivity.

Using Menger's theorem, it becomes straightforward to prove several facts about vertex and edge connectivity. Here is one such example.

2-Connectivity

Block Structure of Connected Graphs

A cut-vertex in a multigraph \( G \) is a vertex \( v \) such that the edge set \( E(G) \) can be partitioned into disjoint, non-empty sets \( E_1 \) and \( E_2 \) such that \( v \) is the only vertex that is incident with edges in both \( E_1 \) and \( E_2 \).

A block is a connected multigraph with no cut-vertex. Examples of blocks include every loopless and 2-connected multigraph. A block of a multigraph \( G \) is defined as a maximal submultigraph that is a block.

Given a multigraph, we define a graph \( F \) as follows: \( V(F) = \mathcal{B} \cup \mathcal{C} \), where \( \mathcal{B} \) is the set of all blocks of \( G \), and \( \mathcal{C} \) is the set of all cut-vertices of \( G \). A block \( B \in \mathcal{B} \) is adjacent to a cut-vertex \( c \in \mathcal{C} \) if \( c \in V(B) \). This is called the block structure of a graph.

Matching

Matchings in General

A matching in a graph \( G \) is a set of edges \( M \subseteq E(G) \) such that every vertex of \( G \) is incident with at most one edge of \( M \).

• \( M \) saturates a vertex \( v \in V(G) \) (or \( v \) is saturated by \( M \)) if \( v \) is incident with an edge of \( M \).
• A matching is perfect if it saturates every vertex in the graph.
• A maximum matching is a matching \( M \) in \( G \) such that there is no matching \( M' \) with \( \#M' > \#M \).
• A maximal matching is a matching \( M \) such that there is no matching \( M' \) with \( M \subsetneq M' \) (i.e., it cannot be extended by adding more edges).

An M-alternating path is a path \( P \) such that edges in \( M \) and edges not in \( M \) alternate along \( P \). An M-augmenting path is an \( M \)-alternating path \( P \) that starts and ends in an \( M \)-unsaturated vertex.

Notice that if we have an \( M \)-augmenting path \( P \), we may construct a new matching using the operation of symmetric difference $$ M' := M \, \Delta \, E(P) = \left( M \setminus E(P) \right) \cup \left( E(P) \setminus M \right). $$ It is straightforward to check that the set \( M' \) is indeed a new matching which satisfies \( \#M' > \#M \); since the path \( P \) starts and ends with non-matching edges, flipping the edges along the path yields one more matched edge than before.

Matchings in Bipartite Graphs

Let \( G \) be a bipartite graph with a vertex bipartition \( V(G) = A \sqcup B \). A matching \( M \) is a complete matching from \(A\) to \(B\) if it saturates every vertex of \( A \). If \( \#A = \#B \), then a complete matching from \( A \) to \( B \) is the same as a perfect matching.

For any subset \( S \subseteq A \), let \( \Gamma(S) \) denote the neighborhood of \( S \), defined as: $$ \Gamma(S) := \{ v \in B \mid v \text{ is adjacent to a vertex in } S \} $$ Notice that if \( \#\Gamma(S) < \#S \) for some \( S \subseteq A \), then a complete matching from \( A \) to \( B \) is strictly impossible, because there are not enough distinct neighbors in \( B \) to partner with the elements of \( S \). This is the fundamental obstruction to bipartite matching.

A vertex cover in a graph \( G \) is a set of vertices \( C \subseteq V(G) \) such that every edge in \( G \) is incident to at least one vertex in \( C \).

Because every edge in a matching \( M \) is disjoint, any vertex cover must pick at least one distinct vertex for every edge in \( M \). Therefore, in any graph, the size of a maximum matching is always less than or equal to the size of a minimum vertex cover (\( \#M \le \#C \)). In bipartite graphs, these two quantities are exactly equal.

Stable Matching

Let \(A = \{ \text{Hospitals} \}\) and \(B = \{ \text{Med Students} \}\). Form a complete bipartite graph \(G\) with \(V(G) = A \sqcup B\). Each hospital ranks all students in order of preference: if \(a \in A\) prefers \(b' \in B\) over \(b \in B\), we write \(b' >_a b\). Similarly, we denote a student's have preferences determined by ranking all hopsticals in \( B \), and we write \(a' >_b a\) if student \( b \) prefers hospital \( a' \) to \( a \).

A matching \(M \subseteq G\) is stable with respect to the given preferences if there are no opportunities to renege on offers; in other words, for every non-matching edge \(ab \in E(G) \setminus M\), at least one of the following is true:

• There exists \(b' \in B\) such that \(ab' \in M\) and \(b' >_a b\)
• There exists \(a' \in A\) such that \(a'b \in M\) and \(a' >_b a\)

The proof of this result is algorithmic: we can construct a stable matching by an alternating sequence of rounds as follows.

• Odd Rounds: Each hospital makes an offer to their preferred student among those who have not already rejected them.
• Even Rounds: Each student rejects all offers received except the one they most prefer.

Proposition: For \(m = \# A\) hospitals and \(n = \# A\) med students, there are at most \(mn\) rounds.

By similar reasoning, when \( m \le n \) all \( m \) hospitals are matched with students and when \( n \le m \) all students are matched with hospitals. Thus, the matching \( M\) constructed by this process is complete. It remains to show that \( M\) is stable. To see this, let \( ab \in E(G)\) be a non-matched edge. This means that \( a \) is matched in \( M\) with some other \( b ' \in B \) or \( b\) is matched with some other \( a ' \in A\). We now ask: did \( a \) ever made an offer to \( b \)? If so, then it must be the case that \( b \) preferred \( a' \), and if not then \( a \) must haveve preferred \( b' \). In either scenario, the required stability condition holds.

By similar reasoning, when \(m \le n\) all \(m\) hospitals are matched with students, and when \(n \le m\) all students are matched with hospitals. Thus, the matching \(M\) constructed by this process is maximal. It remains to show that \(M\) is stable. To see this, let \(ab \notin M\) be a non-matched edge. This means that \(a\) is matched in \(M\) with some other \(b' \in B\), or \(b\) is matched with some other \(a' \in A\). We now ask: did \(a\) ever make an offer to \(b\)?

• If yes: Since \(ab \notin M\), \(b\) must have rejected \(a\)'s offer at some point. Students only reject offers if they already hold or receive a better one, and their retained offers only improve over time. Therefore, \(b\)'s final match \(a'\) must be strictly preferred over \(a\), meaning \(a' >_b a\).
• If no: Hospitals make offers in strictly decreasing order of preference. Since \(a\) never reached the point of offering to \(b\) before the algorithm terminated, \(a\)'s final match \(b'\) must be strictly higher on its preference list than \(b\), meaning \(b' >_a b\).

In either scenario, the required stability condition holds, proving the graph has no blocking pairs.

Example:

Consider the following preference rankings for 3 Hospitals (MU, UNL, KU) and 3 Students (Alice, Bob, Chad):

If we run the Gale-Shapley algorithm, the outcome changes drastically depending on who does the proposing.

6. Graph Coloring

Basic Definitions and Examples

A proper vertex coloring of a graph \( G \) is a function \( c \) that maps \( V(G) \) to some set of colors \( S \) in such a way that if \( uv \in E(G) \), then \( c(u) \neq c(v) \). When the context is clear, we simply use the term coloring. We say \( c \) is a \( k \)-coloring if \( \# S \le k \).

The chromatic number of \( G \), denoted by \( \chi(G) \), is the smallest positive integer \( k \) such that \( G \) has a \( k \)-coloring. Notice the following:

• \( \chi(G) = 1 \iff E(G) = \emptyset \)
• \( \chi(G) \le 2 \iff G \) is bipartite. (Indeed, if \( G \) is bipartite, then all edges have the form \(ab \) with \( a \in A, b \in B\), and we may use one color for \(A \) vertices and another for \(B \) vertices. Conversely, given a \( 2 \) coloring of \( G\)'s vertices, we can set \( A \) to be the set of all vertices receiving one color and \( B\) to be the set of vertices receiving the other color.)

All known proofs of this theorem are very difficult, relying on extensive computer calculations. You can learn more about the fascinating history of this result by clicking the link below.

Greedy Coloring and Bounds on the Chromatic Number

A simple way to color a graph is to order the vertices \( v_1, v_2, \dots, v_n \). Having colored \( v_1, \dots, v_{i-1} \), we color \( v_i \) using the least available color (the smallest positive integer not already used by its neighbors).

Corollary: Since the maximum degree \( \Delta(G) \ge \delta(H) \) for all subgraphs \( H \), it immediately follows that \( \chi(G) \le \Delta(G) + 1 \).

The bound \( \chi(G) \le \Delta(G) + 1 \) is tight for complete graphs and odd cycles, but for most other graphs, we can do better.

The Chromatic Polynomial

While the chromatic number tells us the minimum number of colors required to color a graph, we can also ask a broader combinatorial question: given a set of \( k \) available colors, in how many distinct ways can we properly vertex-color the graph? This counting function is denoted by \( \chi_G(k) \). For any graph \( G \), \( \chi_G(k) \) can be expressed as a polynomial in the variable \( k \), and is thus known as the chromatic polynomial.

Examples:

• Complete Graph \( K_n \): Every vertex is adjacent to every other vertex, meaning all \( n \) vertices must receive a different color. The first vertex has \( k \) available choices, the second has \( k-1 \), the third has \( k-2 \), and so forth. Thus, the chromatic polynomial is \( \chi_{K_n}(k) = k(k-1)(k-2)\cdots(k-n+1) \).
• Empty Graph \( \overline{K_n} \): Because there are no edges present, the color choice for any vertex is completely independent of the others. Each of the \( n \) vertices has \( k \) unrestricted choices. Thus, \( \chi_{\overline{K_n}}(k) = k^n \).
• Trees: For any tree \( T \) on \( n \) vertices, we can pick an arbitrary root and color it in \( k \) ways. We then color the remaining vertices by traversing outward from the root. Because a tree contains no cycles, each new vertex we visit is adjacent to exactly 1 already-colored vertex (its parent), leaving exactly \( k-1 \) valid color choices. Thus, \( \chi_T(k) = k(k-1)^{n-1} \).

Planar Graphs

A plane graph is a graph \( G \) satisfying the following topological properties:

• \( V(G) \subseteq \mathbb{R}^2 \).
• For every edge \( e \in E(G) \) with ends \( u \) and \( v \), there exists a continuous curve \( C_e \) with ends \( u \) and \( v \) such that \( e = C_e \setminus \{u,v\} \subseteq \mathbb{R}^2 \setminus V(G) \).
• If \( e, e' \in E(G) \) are distinct, then their intersection is empty (\( e \cap e' = \emptyset \)).

Consequently, an edge of a plane graph is a subset of the plane that includes no vertices, not even its own endpoints. A graph is planar if it is isomorphic to a plane graph, which we refer to as a planar drawing. The faces of a plane graph \( G \), denoted \( F(G) \), are the connected components of \( \mathbb{R}^2 \setminus G \). (Note: Our proofs in this section depend on an intuitive grasp of "connected sets" in \( \mathbb{R}^2 \). The term "connected" can be formalized using the language of topology.)

Here, we have $$ \# E (G) = 9 > 2 \cdot 6 - 4. $$

Surprisingly, \(K_5 \) and \(K_{3,3} \) are, in some sense, universal examples of non-planar graphs. This is the content of Kuratowski's Theorem, which we now state without proof. A subdivision of a graph \( H \) is obtained by replacing its edges with internally disjoint paths of nonzero length. An \( H \)-subdivision in \( G \) is a subgraph of \( G \) isomorphic to a subdivision of \( H \).

Ramsey Theory

Observation (The Party Problem): Out of 6 people at a party, either some 3 know each other, or some 3 don't know each other. In graph-theoretic terms, if \( |V(G)| = 6 \), then either \( \omega(G) \ge 3 \) (a clique of size 3) or \( \alpha(G) \ge 3 \) (an independent set of size 3).

Here, \( n = 6 \) is the absolute "best possible" (smallest) number to guarantee this property. If we only have 5 people, it is possible to construct a graph with neither a \( K_3 \) nor an independent set of size 3. The standard counterexample is the 5-cycle (\( C_5 \)). Alternatively, one may phrase this result in terms of non-proper \(2\)-colorings of the line graph \( L(K_n) \). This is the graph with vertex set \( E(K_n) \), where \( e, e' \in E(K_n) \) are adjacent if they share an end in \( K_n \). The result then states that any (non-proper) \( 2 \)-coloring of \( L(K_n) \) for \( n \ge 6 \) must contain a monochromatic triangle, while for \( n < 6 \) a monochromatic triangle need not exist.

Definition: Given integers \( k, l \), let the Ramsey Number \( r(k, l) \) denote the smallest integer \( n \) such that every graph \( G \) on \( n \) vertices has either \( \omega(G) \ge k \) or \( \alpha(G) \ge l \).

The party problem establishes that \( r(3, 3) = 6 \). We also have trivial base cases: \( r(k, 1) = 1 \) and \( r(k, 2) = k \) (for \( k \ge 2 \)). Furthermore, by symmetry, \( r(k, l) = r(l, k) \).

Very little is known about the exact values of Ramsey numbers. For example, when \( k = l = 5 \), it has been shown with the help of computer search that $$ 43 \le r(5,5) \le 46. $$ See here for a recent development. Still, despite substantial effort, the exact value is still unknown.