Notes on Graph Theory

Published Sep 30, 2022

Graph Theory, as the name suggests, is the study of graphs. But what exactly is a graph?

Definition

A simple graph $G$ consists of a vertex set (not necessarily finite) $V$ and a finite edge set $E$ consisting of doubletons of $V$.

This is a simple graph. The figure above shows a visualization of six vertices (also called nodes), connected by seven edges. A graph is simple if and only if it does not have more than one edge between any two vertices and no edge starts and ends at the same vertex.

We can extend simple graphs to allow more variety, such as multigraphs (nodes are allowed to be connected by multiple edges), pseudographs (self-connecting loops are also allowed), and hypergraphs (one edge can connect multiple nodes). Unless otherwise stated, assume any graphs are simple by convention in what follows.

Often, we also assign properties to vertices and edges. For example, in a directed graph, edges point specifically from one vertex to another. Edges and nodes might also have a weight, color, etc, assigned to them. Then we can optimize some function of these parameters in a subgraph satisfying some properties.

Applications of Graph Theory

It is relatively easy to see that graphs serve as good models for networks, and networks are interesting long before the advent of computers. One of the oldest problems in this theory goes back to Euler.

The Konisberg Bridge Problem

Can one start on one of the islands, cross each bridge exactly once, and end back on the original island?

Of course, we can model each island as a node and bridges as edges between the nodes. In fact, here we have a multigraph that is not simple.

This question was famously answered in the negative by Leonhard Euler. His solution to the problem laid the foundations for Graph Theory and conceptually, Topology. To this day, the two fields remain closely connected, despite being studied by disparate groups of mathematicians.

Planar graphs

The above image might inspire one to wonder: Are all graphs expressable as a 2-dimensional drawing?

Certainly one can project any graph onto the plane with no regard for structure, but mathematicians are interested in a more sophisticated question: Are all graphs expressable as a 2-dimensional drawing such that no edges intersect?

The answer is actually no, and graphs that do satisfy this property are called planar.

See Kuratowski’s Theorem for related info on the characterization of planar graphs.

Four Color Theorem

Many people are probably familiar with the Four Color Theorem, given it’s popularity with pop-science. The (layman) statement is quite simple, all ‘maps’ can be colored with four colors such that no two boundaries that share an edge are monochromatic. However, the proof and underlying mathematical reasonings are far from simple.

• The Six color theorem could be proven with half a page, and is a common exercise for a first year Graph Theory course.
• Five color theorem: Substantially harder, perhaps suitable as a research assignment.
• Four color theorem: Very difficult, and we still don’t have a pure pen and paper proof. A very large finite amount of cases were checked computationally.

Graph Isomorphism

Here’s a problem of high modern significance:

Graph Isomorphism Problem

Can you rearrange vertices without changing edge pairs to morph one graph into another?

It turns out solving this problem is quite difficult, and so far mathematicians have only been able to produce an algorithm in Quasi-polynomial time complexity. This problem has surged in popularity due to its relevance with P vs NP; A polynomial algorithm or lack thereof is relatively within reach and would contribute substantial progress towards the famous unsolved computer science problem.

Traversal

Paths, Walks, and Cycles

Let $G = (V, E)$ be a simple graph. A walk is defined as a sequence of vertices $\{P\}_{i = 1}^{k}$ of vertices $p_i \in V$, where $p_i, p_{i + 1}$ are connected by an edge $e \in E$ for all $i \in [1, k - 1]$. One could “walk” along these vertices consecutively and in order.

A path is a walk where $P$ contains no duplicate elements; $p_i$ are pairwise distinct.

A cycle is a sequence $\{Q\}_{i = 1}^{k}$ such that $\{Q\}_{i = 1}^{k - 1}$ is a path and $q_k = q_1$.

Connectivity

A simple graph $G = (V, E)$ is connected if for any two vertices $v, w \in V$, there exists a path connecting $v$ and $w$.

A connected component is a subgraph $g \in G$ such that $g$ is connected. In most cases, we can assume the graph we are working with is connected, as each connected component in an unconnected graph can usually be treated seperately.

Travelling Salesman

In the Konisberg Bridge Problem, we were asked, Can we traverse all the edges exactly once, and return to our starting node?

In most cases, however, we are more concerned with

Can we traverse all the nodes exactly once, and returning to our starting node?

Such a traversal is called a Hamiltonian Cycle. A graph that has such a cycle is considered Hamiltonian.

Exercise (Dirac's Theorem):

If every vertex $v$ in a simple graph $G$ satsifies $\deg{v}$ $\geq \vert V \vert / 2$, $G$ is Hamiltonian.

Of practical signficance is the widely-studied Travelling Salesman Problem, where we further assign a cost to each edge. Now this into an optimization problem, where we not only consider whether or not it is possible to have a Hamiltonian Cycle, but to find the cycle with minimum cost.

To learn more about graph traversal, commonly appearing in informatics competitions, see the USACO Silver Guide and Gold Guide.

Density

A basic result concerning connected graphs is the following: $\vert E \vert \geq \vert V \vert - 1$. The theorem is sharp in the sense that equality is achieveable, in the form of Trees.

If a graph is “too sparse”, it can’t be connected.

Trees

A simple connected graph $G = (V, E)$ is said to be a Tree if any of the following are satisfied:

• $\vert E \vert = \vert V \vert - 1$
• $G$ has no cycles.
• For each pair of distinct vertices $v, w$ there is a unique path starting at $v$ and ending at $w$.

Exercise:

Prove that the three above definitions are equivalent.

On the other end of the spectrum, we have complete graphs, where there is an edge betwen every node. This the densest possible simple graph. These two special types of graphs are immensely useful.

Degrees and Neighborhoods

An adjacent vertex of $v \in V$, is a vertex connected to $v$ by an edge. The degree of a vertex $v$, denoted $\deg{v}$, is the number of adjacent vertices of $v$. The neighbourhood of $v$ is the subgraph of $G$ composed of all vertices adjacent to $v$ (does not include $v$ itself) and all edges connecting those vertices.

If we have a directed graph, we can be more specific with degrees. The outdegree, denoted $\deg^+{v}$, is the number of adjacent vertices $w$ with an edge pointing from $v$ to $w$. Analogously, the indegree ($\deg^-{v}$) is the number of adjacent vertices $w$ with an edge pointing from $w$ to $v$.

Handshaking Lemma

For a finite undirected graph $G = (V, E)$,

Take a moment to convince yourself the lemma is true.

Exercise:

In a finite undirected graph, prove that the number of vertices that have odd degree is even.

We also have the following two identities:

In a directed graph,

In a tournament, a complete directed graph,

Exercise:

Prove the above identities.

Problem (2010 IMO Shortlist C5):

$n \geq 4$ players participated in a tennis tournament. Any two players have played exactly one game, and there was no tie game. We call a company of four players bad if one player was defeated by the other three players, and each of these three players won a game and lost another game among themselves. Suppose that there is no bad company in this tournament. Let $w_i$ and $l_i$ be respectively the number of wins and losses of the $i$-th player. Prove that

$$\sum^n_{i=1} \left(w_i - l_i\right)^3 \geq 0$$

The Complete Graph

The complete graph with $n$ vertices, denoted as $K_n$, is a simple connected graph such that there is an edge between any two vertices. The complete graph is analogous to the symmetric group of group theory, in that it serves as a “mother of all graphs”. In other words, every finite simple graph can be realized as the subgraph of a complete graph. More precisely, every finite simple graph can be obtained from a complete graph by keeping the same vertex set and removing some edges from the edge set.

Exercise:

How many edges does $K_n$ have? How many subgraphs with $n$ vertices?

Extremal Graph Theory

Complete graphs are also one of the central objects studied in extremal graph theory, which asks: What is the largest/smallest graph with some kind of property? Some significant results have come from studying graphs with no complete subgraph.

Mantel's Theorem:

The maximum number of edges in a graph on $n$ vertices that does not have a subgraph $K_3$ is $\lfloor n^{2}/4 \rfloor$.

You can try proving this with induction, noting the equality case of a complete bipartite graph, a bipartite graph $V = A \cup B$ with an edge connecting every pair of vertices $(a \in A, b \in B)$. Turan’s Theorem generalizes this result.

Graph Colorings

Complete graphs serve as the perfect setting to discuss graph colorings, which form a very popular class of contest problems. A vertex/edge coloring is an assignment for some finite set of colors $\mathcal{C}$, where it assigns each vertex/edge a color.

Size of the color set determines the order of the coloring.

We say that a graph $G = (V, E)$ is $k$-colorable if one can color the vertices of $G$ using at most $k$ colors so that there are no monochromatic edges: that is, for each edge $e \in E$ the two endpoints of $e$ have distinct colors.

The chromatic number of $G$ is the least integer $k$ such that $G$ is $k$-colorable.

Colorability of the complete graph $K_n$.

The complete graph $K_n$ is $n$-colorable but not $(n - 1)$-colorable.

The proof is simple: It is obviously $n$-colorable, as we can color each vertex a different color. It is not however $(n - 1)$-colorable as by the pigeonhole principle 2 vertices must share a color, but they must also be connected by an edge by definition.

Exercise:

Prove the converse. That is, if a simple graph on $n$ vertices is not $(n - 1)$-colorable, it is $K_n$.

Planar Graph Colorings

There’s an intuitive notion that graph colorings and topology should be intimately connected. This is motivated by the Map Coloring problem, posed by South African mathematician William Gilmour Guthrie in 1872. The problem arises exactly as the name suggests: when coloring a map (Guthrie was trying to color a map of England), how many colors must be available to guaratee that no two contiguous regions share the same color?

You probably already know the answer.

The Four Color Theorem, again

We are now in a position to restate this theorem with more sophisticated language: All planar graphs are 4-colorable.

In planar graphs, we also have the notion of faces, the regions of space bounded by edges. Faces can be unbounded. Note that they are not the same as regions in maps, which are actually expressed as nodes in planar graphs.

Exercise (Face-Shaking Lemma):

Consider a connected planar graph $G = (V, E, F)$. For a face $f \in F$ let $\alpha(f)$ be the number of edges enclosing $f$. Then

$$\sum_{f \in F} \alpha(f) = 2 |E|$$

Exercise:

Prove that for a connected planar graph $G = (V, E, F)$, that

$$|E| \leq 3 |V| - 6$$

We also have the powerful Euler’s Formula.

Euler's Formula:

In a connected planar graph,

$$|V| - |E| + |F| = 2$$

Consider $n$ lines in the plane, no two parallel and no three concurrent. Convince yourself of Euler’s Formula. You might find that $|V| - |E| + |F| = 1$. In this context, we can imagine the unbounded line segments converge at an extra vertex at infinity.

Exercise:

Suppose $G = (V, E, F)$ is a connected planar graph with a cycle. The length of the smallest cycle is called the graph’s girth, $g$. Prove,

$$|E| \leq \frac{g}{g - 2} (|V| - 2)$$

Bipartite Graphs

A bipartite graph is a graph that is 2-colorable.

Exercise:

A simple finite graph $G = (V, E)$ is bipartite if and only if there exists no odd cycles.

Solution:

A cycle $C_k$ is bipartite if and only if $k$ is even (Why?). Thus there are no odd cycles if $G$ and thus any $C_k$ is bipartite.

Now we tackle the harder direction: If $G$ is not bipartite then there must exist an odd cycle. Consider connected components $C = (P \in V, Q \in E) \in G$ seperately. Take any vertex $v$ in $P$, assign it a color, and alternate colors assignments by depth. For $C$ to not be bipartite, there must exist adjacent vertices $a_0, b_0 \in P$ that are monochromatic. Since $C$ was colored by depth, $a_0$ cannot be colored directly from $b_0$. Hence it must be colored from some $a_1 \in P$, and similarly $b_0$ must be colored from some $b_1 \in P$. If $a_1 = b_1$ then we are done, otherwise continue to $a_2, b_2$ and so on. Since $G$ and thus $C$ is finite, there must exist $n$ such that $a_n = b_n$. The cycle $(a_0, a_1, \cdots, a_{n - 1}, a_n = b_n, b_{n - 1}, b_{n - 2}, \cdots b_0, a_0)$ is odd and we are done.

Bipartite graphs are extremely applicable in the real world, because they model a lot of natural assignment problems. One of the basic questions that can be modelled by bipartite graphs is the following: Suppose at a worksite there are $m$ workers and $n$ different types of tasks that need to be completed (the tasks could involve electrical work, carpentry, transporting, etc.). For each worker $w$ there are certain tasks they can do, but they can only do one task at a time. How would one assign tasks to the workers as to minimal idling (i.e., as many workers should be working as possible) and no overlaps (i.e, each task should be done by at most one worker)?

We can restate this in graph theory. A vertex cover in a graph is a set of vertices that includes at least one endpoint of every edge, and a vertex cover is minimum if no other vertex cover has fewer vertices. A matching in a graph is a set of edges no two of which share an endpoint, and a matching is maximum if no other matching has more edges. So, in the general example above: Given a bipartite graph, what is the optimal matching satisfying some conditions?

As one can imagine, above question is analogous to many other applications, like assigning workers to employers, or applicants to colleges. Given their practical significance, there is a lot of interest in finding matchings which are somewhat optimal.

Konig's Theorem:

In a bipartite graph, the number of edges in a maximal matching is equal to the number of vertices in a minimal vertex cover.

Although interesting, the notion of vertex covers is hardly every relevant in math olympiads due to its relative obscurity and counter-intuitive definition.

Hall’s Marriage Theorem

Hall’s Marriage Theorem characterizes the existance of perfect matchings. It is also a powerful tool in olympiads.

Perfect Matching

Let $G = (V, E)$ be a bipartition $V = A \cup B$ (where $A$, $B$ denotes the 2 partitions). A perfect $A$-matching is a matching such that every vertex in $A$ is matched to a vertex in $B$.

Note that a perfect $A$-matching exists only if $\vert A \vert \leq \vert B \vert$.

Statement

Hall's Theorem:

Let $G = (V, E)$ be a bipartition $V = A \cup B$. Define $N(W)$ as the neighborhood of of a subset of vertices $W$. Then $G$ has a perfect $A$-matching if and only if for every subset $W$ in $A$ we have

$$\vert W \vert \leq \vert N(W) \vert$$

In other words, a perfect $A$-matching exists if and only if for every subset $W$ of $A$, $W$ has at least as many neighbours in $B$ as $\vert W \vert$.

Bipartite Problems

Bipartitions, matchings, and Hall’s Theorem are common in olympiad combinatorics. For questions applying Hall’s, the difficulty is usually in formulating the question in a graph-theoretic way and finding the correct bipartition.

Problem:

A Latin rectangle is an $m \times n$ array with $m \leq n$, such that each row and column consists of distinct numbers from the set $N = \{1, 2, \cdots , n\}$. Prove for any Latin rectangle $\mathcal{L}$ that $\mathcal{L}$ can be extended to an $n \times n$ Latin square.

Problem (2012 Putnam B3):

A round-robin tournament of $2n$ teams lasted for $2n - 1$ days, as follows: On each day, every team played one game against another team, with one team winning and one team losing in each of the $n$ games. Over the course of the tournament, each team played every other team exactly once. Can one necessarily choose one winning team from each day without choosing any team more than once? Prove or provide a counterexample.

Problem (2017 RMM Q5):

Fix an integer $n \geq 2$. An $n\times n$ sieve is an $n\times n$ array with $n$ cells removed so that exactly one cell is removed from every row and every column. A stick is a $1\times k$ or $k\times 1$ array for any positive integer $k$. For any sieve $A$, let $m(A)$ be the minimal number of sticks required to partition $A$. Find all possible values of $m(A)$, as $A$ varies over all possible $n\times n$ sieves.

Challenge (2019 Canada MO Q5):

A 2-player game is played on $n \geq 3$ points, where no three points are collinear. Each move consists of selecting 2 of the points and drawing a new line segment connecting them. The first player to draw a line segment that creates an odd cycle loses. (An odd cycle must have all its vertices among the $n$ points from the start, so the vertices of the cycle cannot be the intersections of the lines drawn). Find all $n$ such that the player to move first wins.