Introduction to Graph Theory

Graph theory studies networks made of points joined by lines, and it powers everything from Google Maps and social media to circuit design and scheduling. It is a core topic in discrete mathematics and computer science courses at university. This introduction covers the essential vocabulary, key theorems and a classic shortest-path algorithm, with complete worked examples.

What Is a Graph?

A graph \( G = (V, E) \) consists of a set of vertices \( V \) (also called nodes) and a set of edges \( E \), where each edge joins two vertices.

• Two vertices joined by an edge are adjacent.
• A loop joins a vertex to itself; multiple edges join the same pair twice. A simple graph has neither.
• In a directed graph, edges have a direction (like one-way streets).
• In a weighted graph, each edge carries a number, such as distance or cost.

Degree

The degree of a vertex, \( \deg(v) \), is the number of edges meeting it (a loop counts twice).

The Handshaking Lemma

Every edge has two ends, so it adds 1 to the degree of each of its two endpoints. Therefore

$$ \sum_{v \in V} \deg(v) = 2|E| $$

An important consequence: every graph has an even number of vertices of odd degree, because the total degree is even.

Worked Example 1: Using the Handshaking Lemma

(a) A simple graph has degree sequence 3, 3, 2, 2, 2. How many edges does it have?

$$ \sum \deg(v) = 3 + 3 + 2 + 2 + 2 = 12 $$

$$ |E| = \frac{12}{2} = 6 $$

(b) Can a graph have degree sequence 3, 3, 3, 2, 2?

$$ 3 + 3 + 3 + 2 + 2 = 13 $$

The sum is odd, but it must equal \( 2|E| \), which is even. So no such graph exists. Equivalently, it would have three vertices of odd degree, which is impossible.

Special Types of Graph

• Complete graph \( K_n \): every pair of the \( n \) vertices is joined. It has

$$ |E| = \binom{n}{2} = \frac{n(n-1)}{2} $$

edges. For example, \( K_5 \) has \( \frac{5 \times 4}{2} = 10 \) edges.

• Bipartite graph: vertices split into two groups, with edges only between groups.
• Connected graph: there is a path between every pair of vertices.
• Tree: a connected graph with no cycles. A tree with \( n \) vertices always has exactly \( n - 1 \) edges, and there is exactly one path between any two vertices.

Walks, Paths and Cycles

A walk is a sequence of vertices where each consecutive pair is joined by an edge. A path is a walk with no repeated vertices. A cycle is a closed path that returns to its start.

Euler Paths and Circuits

Graph theory began in 1736 when Euler asked whether one could walk around Königsberg crossing each of its seven bridges exactly once. In modern language:

• An Euler circuit uses every edge exactly once and returns to the start.
• An Euler path uses every edge exactly once but may end elsewhere.

Euler's theorem (for connected graphs):

1. An Euler circuit exists if and only if every vertex has even degree.
2. An Euler path (but no circuit) exists if and only if exactly two vertices have odd degree; the path must start at one and end at the other.

The Königsberg graph had four vertices, all of odd degree (5, 3, 3, 3), so no such walk is possible.

Worked Example 2: Finding an Euler Path

A connected graph has vertices \( A, B, C, D \) and edges \( AB, AC, BC, BD, CD \). Does it have an Euler path or circuit?

Step 1: Find the degrees.

• \( A \): edges \( AB, AC \), so \( \deg(A) = 2 \)
• \( B \): edges \( AB, BC, BD \), so \( \deg(B) = 3 \)
• \( C \): edges \( AC, BC, CD \), so \( \deg(C) = 3 \)
• \( D \): edges \( BD, CD \), so \( \deg(D) = 2 \)

Check: \( 2 + 3 + 3 + 2 = 10 = 2 \times 5 \) edges.

Step 2: Apply Euler's theorem. Exactly two vertices (\( B \) and \( C \)) have odd degree, so there is an Euler path but no Euler circuit. It must start at \( B \) and end at \( C \), or vice versa.

Step 3: Construct it.

$$ B \to A \to C \to B \to D \to C $$

This uses \( BA, AC, CB, BD, DC \), all five edges exactly once.

Shortest Paths: Dijkstra's Algorithm

In a weighted graph, Dijkstra's algorithm finds the shortest distance from a starting vertex to every other vertex (provided all weights are non-negative).

1. Give the start distance 0 and every other vertex distance \( \infty \).
2. Pick the unvisited vertex with the smallest distance and mark it visited.
3. For each neighbour, if current distance + edge weight is smaller than its recorded distance, update it.
4. Repeat until all vertices are visited.

Worked Example 3: Dijkstra Step by Step

Find the shortest path from \( A \) to \( E \) in a graph with edges \( AB = 4 \), \( AC = 2 \), \( BC = 1 \), \( BD = 5 \), \( CD = 8 \), \( CE = 10 \), \( DE = 2 \).

Step 1: Visit \( A \) (distance 0). Update neighbours: \( B = 4 \), \( C = 2 \).

Step 2: Visit \( C \) (smallest, distance 2). Update:

• \( B \): \( 2 + 1 = 3 < 4 \), so \( B = 3 \)
• \( D \): \( 2 + 8 = 10 \), so \( D = 10 \)
• \( E \): \( 2 + 10 = 12 \), so \( E = 12 \)

Step 3: Visit \( B \) (distance 3). Update \( D \): \( 3 + 5 = 8 < 10 \), so \( D = 8 \).

Step 4: Visit \( D \) (distance 8). Update \( E \): \( 8 + 2 = 10 < 12 \), so \( E = 10 \).

Step 5: Visit \( E \) (distance 10). Done.

The shortest route is

$$ A \to C \to B \to D \to E $$

with total length \( 2 + 1 + 5 + 2 = 10 \). Notice that the direct-looking route \( A \to B \) (length 4) was beaten by going through \( C \) (length 3).

Common Mistakes

• Counting a loop's degree as 1. It contributes 2.
• Ignoring connectivity when applying Euler's theorem. A disconnected graph has no Euler circuit even if all degrees are even (unless the extra components are isolated vertices).
• Finalising a vertex too early in Dijkstra's algorithm. Only the smallest unvisited distance is final.
• Using Dijkstra with negative weights. It can give wrong answers; use Bellman–Ford instead.

Key Takeaways

• A graph is a set of vertices joined by edges; degree counts edges at a vertex.
• Handshaking lemma: the sum of degrees equals \( 2|E| \), so odd-degree vertices come in pairs.
• A tree on \( n \) vertices has \( n - 1 \) edges, and \( K_n \) has \( \frac{n(n-1)}{2} \) edges.
• Euler circuits need all even degrees; Euler paths need exactly two odd-degree vertices.
• Dijkstra's algorithm finds shortest paths in graphs with non-negative weights.

If graph theory problems or a discrete maths assignment are giving you trouble, send them to Amathify on WhatsApp or through the "Ask a Question" form. Our experts and PhD scholars will provide clear, step-by-step solutions.