An introduction to Graph theory

Graph Theory is a branch of mathematics and computer science that deals with modelling various relationships using vertices and edges. Graph theory as a field is crucial today, and is used everywhere we go - from searching the internet to artificial intelligence, and from DNA sequencing to Google Maps. The power of graph theory emerges from its simplicity. Despite being a concept that is fairly simple to understand, it is an active field of research with hundreds of open problems which mathematicians work on today. 

Introduction

The Königsberg Bridge Problem

The city of Königsberg is located on the Pregel river in Prussia. As shown in the image (a) below, the river divided the city into 4 landmasses which were connected by seven bridges. The citizens often wondered if it was possible to start from home, travel through the city crossing every bridge exactly once and return home.

Exercise: Find a round trip crossing each bridge exactly once, or try to prove that no such trip exists.

The problem was first solved by Euler who gave rise to the technique of Graph Theory using this problem. Essentially, he imagined each landmass as a point (vertex) and joined the points with lines (edges) based on the bridges as shown in figure (b). The round trip of the city, in this graph theoretical form is now famously known as an Eulerian Circuit. If you're curious, you can read more about them online here

Thus, we describe a graph using its set of vertices  and edges which connect pairs of vertices.

Why Graphs?

The concept of graph theory from the point of view of vertices and edges is fairly simple and raises questions as to how this could actually be useful. Graph theory is a topic that can often throw in surprises, coming up in unexpected ways and allowing you to analyse conditions in a new and often much simpler way.

The Definitions

Definition: Mathematically, we describe a graph $G$ by its set of vertices $V$ and edges $E$, i.e, $$G=(V,E)$$

As described above, vertices are essentially used to  describe certain objects (like landmasses in a map or just people) which are bound together by certain relationships described by edges (being connected by a bridge, or being friends or enemies).

In the image here, $$\{A,B,C,D,E\}$$ represents $V$, the set of vertices. 

The set of edges $E$ is $$\{(A,B), (A,C), (A,D), (B,E)\}$$ since those are the pairs of vertices which are joined by edges.

It's important to note that the geometry here is completely irrelevant to us (most of the time). So changing the positioning of the vertices, or the shape of the line joining two vertices (curved or anything) is irrelevant to us as long as the only 2 things we care about are the same, i.e, we have the same set of vertices and the same set of edges.

There are various terms that allow us to better understand and analyse a graph.

Definition: Two vertices are said to be adjacent if there is an edge connecting them.

So in the above graph, $A$ and $B$ are adjacent, while $B$ and $C$ aren't adjacent.

Exercise: Are each of the pairs $(C,D)$ and $(D,A)$ adjacent?

Definition: The degree of a vertex $d_i$ is the number of vertices it is adjacent to.

Exercise: What is the degree of each of the $5$ vertices in the given graph?

Example [The Handshake Lemma]

Show that the sum of degrees of the $n$ vertices of a graph is even. In particular,

$$\sum_{i=1}^n d_i = 2 |E|$$

where $|E|$ denotes the number of edges in the graph and $d_i$ denotes the degree of the $i$th vertex.

Walkthrough

1.  What happens if we think edge by edge, instead of vertex by vertex?
2. Show that each edge gets counted exactly twice in the LHS and conclude.

Remark: This problem introduces us to one of the most powerful ideas in graph theory - counting in two ways. It's often really powerful to use the fact that thinking of something vertex by vertex, or edge by edge should lead to the same result. This idea works especially well in graph theory and is something that should be on our mind every time we try a graph problem.

Definition:

A path in a graph $G$ is defined to be a sequence of distinct vertices $v_0, v_1, \cdots ,v_t$ such

that $v_0$ is adjacent to $v_1$, $v_1$ is adjacent to $v_2$ and so on so that $v_{t-1}$ is adjacent to $v_t$. In other words, $v_i$ is adjacent to $v_{i+1}$ for all $i \in \{0,1,\cdots t-1\}$. The length of a path is defined to be the number of edges in the path.

So below in figure 3, $D,E,B,C$ forms a path as highlighted.

Exercise: Is there a path between $A$ and $B$ in this new graph?

Definition: A graph is said to be connected if there exists a path from each vertex to each other vertex of the graph.

Exercise: Show that each of the 2 graphs on 5 vertices we have drawn are connected.

Definition: 

A cycle in a graph $G$ is defined to be a sequence of distinct vertices $v_0, v_1, \cdots ,v_t$ such that $v_0$ is adjacent to $v_1$, $v_1$ is adjacent to $v_2$ and so on so that $v_{t-1}$ is adjacent to $v_t$ and $v_t$ is adjacent to $v_0$. In other words, $v_i$ is adjacent to $v_{i+1}$ for all $i \in \{0,1,\cdots t-1\}$ and $v_t$ is adjacent to $v_0$. The length of a cycle is defined to be the number of edges in the cycle.

Here $A-B-C-D-F-A$ is a cycle.

Exercise: Find 3 other cycles in this graph.

A cycle is one of the most important concepts in graph theory. A lot of problems reduce to showing that a cycle exists in a graph. A few interesting lemmas about cycles in graphs are presented as examples as follows.

Example:

Show that a graph with minimum degree $\delta \geq 2$ has a cycle of length atleast $\delta +1$.

Walkthrough

1.  Consider the longest path in the graph. What can we say about its length?
2. Let the path be $$v_0-v_1-v_2-\cdots v_k$$ Can $v_0$ have a neighbour not present in this path?
3. Show that $v_0$ is connected to a $v_i$ in this path with $i \geq \delta$. This completes the proof (why!). 

The most important question to ask here is - Why on earth would anyone think of step one? As it turns out, using maximal structures is an idea that is super useful in graph theory, and in combinatorics in general. Its often useful to think about the longest paths, largest cycles, vertices with maximum degree and so on.

Example:

Let $G$ be a connected graph with $n$ vertices having a cycle. We delete an arbitrary edge of the cycle. Show that the new graph (called an induced subgraph) is connected too.

Walkthrough

Let the edge we deleted be between vertices $A$ and $B$

1.  Try enough examples until you're convinced that this is true.
2.  Assume for the sake of contradiction that the new graph is not connected.
3.  This means that the only path between some two vertices contained the edge we deleted (Why!). So it's enough to find another path between $A$ and $B$. Why does this exist?

We now introduce arguably the most important concept in graph theory - Trees.

Trees

What is a tree?

In the previous example, notice that if we repeatedly apply this process, that is keep removing edges from the cycles present in the graph, we're reducing the number of cycles in the graph so at some point we must reach a stage where there is no cycle left in the graph, but the graph is still connected. This structure of a connected graph with no cycles is called a Tree.

Definition:

Let $G$ be a connected graph with $n$ vertices. The following statements are equivalent, and each of them implies that the graph $G$ is a tree.

• $G$ does not contain any cycles.
• $G$ contains exactly $n-1$ edges
• For any two vertices, there exists exactly one path joining the two vertices

Walkthrough

1. The first one is the way we defined a tree. Show that the third one follows directly (Proceed by method of contradiction)
2. The second one is something we need to prove, and is probably the most useful definition of trees. There are various ways to prove this, but something that is common to a lot of proofs is the method of induction. We explain one such solution below

Solution: Delete an arbitrary edge from the graph. This should split the graph into two trees (why!) that are disconnected from each other. Let them have $k$ and $n-k$ vertices respectively. Now by strong induction, the number of edges in the first part is $k-1$ and in the second part, $n-k-1$. Thus the total number of edges on adding back the edge we deleted is $(n-k-1)+(k-1)+1 = n-1$

Remark: Try inducting by deleting a vertex instead of an edge.

Also, this means that any graph with less than $n-1$ edges cannot be connected, and any connected (or infact any) graph with at least $n$ edges must contain a cycle.

Example [Leaf Nodes in a Tree]

Show that every tree must have atleast one vertex with degree $1$, known as a leaf. Can it have exactly one?

Walkthrough

This problem brings us back to the very first example we did, the handshake lemma. We begin by tackling the first part of the question. 

1.  Assume for the sake of contradiction that each $d_i \geq 2$. What does this make the minimum value of the LHS in the handshake lemma?
2. Why is this a contradiction to the value of the RHS?
3.  Now, for part two, use the same argument to rule out exactly one $d_i=1$ and others $>=2$.

2 Example problems

Problem

Given the graph $G$ and cycle $C$ in it, we can perform the following operation: add another vertex $v$ to the graph, connect it to all vertices in $C$ and erase all the edges from $C$. Prove that we cannot perform the operation indefinitely on a given graph.

Walkthrough

There are multiple ways to approach this, but here's an intutive and quite elegant way.

1.  Let us first assume the graph was connected. We'll see later as to why this was not too problematic an assumption. The operation does not disconnect the graph (why!), so we know that $G$ is always connected. 
2. If this operation is to end, it must be at a tree, which must have $|E| = |V|-1$.
3. What happens to the number of edges and vertices after an operation. What do you conclude?
4. Now lets say $G$ was not connected. Think of any component of $G$ which is connected (!!). We can show that this component will ultimately become a tree, so the graph $G$ will end up as a union of disjoint trees (called a forest).

Remark: With graph theoretic problems, or just combinatorics in general, our aim is often to increase or decrease the amount of structure of a problem, making it more convenient to solve. Assuming $G$ is connected increases the amount of structure, making it easier to make conclusions about the problem.

Here's a very cool olympiad styled problem, all about finding a cycle in a hidden graph.

Problem:

Suppose $2n$ points of an $n\times n$ grid are marked. Prove that there exists a $k > 1$ and $2k$ distinct marked points $$a_1,\cdots, a_{2k}$$ such that, for all $i$, $a_{2i-1}$ and $a_{2i}$ are in the same row,

while $a_{2i}$ and $a_{2i+1}$ are in the same column.

Try this out yourself if you have time! I've tried to cover a lot of fundamental ideas in graphs - hope you all had fun :)

~ Rushil