# Graph Theory — Degrees, Handshaking Lemma, Paths, Euler and Hamiltonian Circuits, Trees, Bipartite and Planar Graphs, Colouring

Source: https://skills101.in/learn/discrete-math/graph-theory-basics — Skills101 free tutorial (Discrete Mathematics). Updated 2026-11-09.

Maps, social networks, the internet, course prerequisites, dependency graphs in build tools — all **graphs**. DSA teaches algorithms on graphs (BFS, DFS, Dijkstra); discrete maths gives the theory and vocabulary behind them.

## 1. Basic terms

A **graph** G = (V, E): **vertices** (nodes) and **edges** connecting pairs of them.

| Term | Meaning |
|---|---|
| Undirected / directed | edges are two-way / one-way (arrows) |
| Weighted | edges carry numbers (distance, cost) |
| Simple graph | no self-loops, no multiple edges between the same pair |
| **Degree** deg(v) | number of edges at v (in-degree/out-degree for directed) |
| Path | sequence of edges with no repeated vertex |
| Cycle | path that returns to its start |
| Connected | a path exists between every pair of vertices |
| Complete graph Kₙ | every pair of vertices connected: n(n−1)/2 edges |

## 2. The handshaking lemma

**The sum of all degrees = 2 × number of edges** (each edge has two ends).

Consequence: **the number of odd-degree vertices is always even.** (So "a party of 7 where everyone shook hands with exactly 3 others" is impossible: 7 × 3 = 21 is odd.)

```python
edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D"), ("D", "E"), ("B", "D")]
degree = {}
for u, v in edges:
    degree[u] = degree.get(u, 0) + 1
    degree[v] = degree.get(v, 0) + 1
print("degrees:", degree)
print("sum of degrees =", sum(degree.values()), "= 2 x edges =", 2 * len(edges))
print("odd-degree vertices:", [v for v, d in degree.items() if d % 2])
```

```text
degrees: {'A': 2, 'B': 3, 'C': 3, 'D': 3, 'E': 1}
sum of degrees = 12 = 2 x edges = 12
odd-degree vertices: ['B', 'C', 'D', 'E']
```

## 3. Euler and Hamiltonian circuits

![Euler versus Hamiltonian: an Euler circuit uses every edge exactly once, possible when every vertex has even degree; a Hamiltonian cycle visits every vertex exactly once, with no simple test for when it exists](https://skills101.in/learn-img/discrete-math/euler-hamilton.svg)

| | Euler | Hamiltonian |
|---|---|---|
| Visits | every **edge** exactly once | every **vertex** exactly once |
| Circuit exists (connected graph) | **all vertices have even degree** | no simple rule — NP-complete to decide |
| Path exists | exactly **0 or 2** odd-degree vertices (start/end at the odd ones) | — |
| Classic | Königsberg bridges (impossible: 4 odd vertices) | travelling salesperson route |

The graph in section 2 has **four** odd-degree vertices (B, C, D, E) — so, just like the Königsberg bridges, it has **neither** an Euler path nor an Euler circuit. A simple square (every degree 2) has an Euler circuit:

```python
from itertools import permutations

def euler_status(edges):
    deg = {}
    for u, v in edges:
        deg[u] = deg.get(u, 0) + 1
        deg[v] = deg.get(v, 0) + 1
    odd = [v for v, d in deg.items() if d % 2]
    return "Euler circuit" if not odd else f"Euler path between {odd}" if len(odd) == 2 else "neither"

def has_hamiltonian_cycle(vertices, edges):
    E = {frozenset(e) for e in edges}
    first, rest = vertices[0], vertices[1:]
    for p in permutations(rest):
        cycle = [first, *p, first]
        if all(frozenset((cycle[i], cycle[i + 1])) in E for i in range(len(cycle) - 1)):
            return cycle
    return None

edges = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D"), ("D", "E"), ("B", "D")]
print(euler_status(edges))
print("Hamiltonian cycle:", has_hamiltonian_cycle(list("ABCDE"), edges))
square = [("1", "2"), ("2", "3"), ("3", "4"), ("4", "1")]
print(euler_status(square), "| Hamiltonian:", has_hamiltonian_cycle(list("1234"), square))
```

```text
neither
Hamiltonian cycle: None
Euler circuit | Hamiltonian: ['1', '2', '3', '4', '1']
```

Vertex E has degree 1, so no cycle can pass through it — no Hamiltonian cycle. The brute-force search tries all orderings (n! of them), which is exactly why Hamiltonian problems are hard for large graphs.

## 4. Trees

A **tree** is a connected graph with **no cycles**. Facts (any one follows from the others):

- a tree with **n vertices has exactly n − 1 edges**;
- there is exactly **one path** between any two vertices;
- removing any edge disconnects it; adding any edge creates a cycle.

A **spanning tree** connects all vertices of a graph using n − 1 of its edges; a **minimum spanning tree** (Kruskal, Prim) does it with least total weight — network cabling, road planning. By **Cayley's formula**, the complete graph Kₙ has **nⁿ⁻² spanning trees**.

## 5. Bipartite graphs

Vertices split into two groups with edges only **between** groups (students ↔ courses, applicants ↔ jobs). **A graph is bipartite iff it has no odd-length cycle** — test it by 2-colouring with BFS:

```python
from collections import deque

def is_bipartite(adj):
    colour = {}
    for start in adj:
        if start in colour:
            continue
        colour[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if v not in colour:
                    colour[v] = 1 - colour[u]
                    q.append(v)
                elif colour[v] == colour[u]:
                    return False
    return True

square = {1: [2, 4], 2: [1, 3], 3: [2, 4], 4: [3, 1]}
triangle = {1: [2, 3], 2: [1, 3], 3: [1, 2]}
print("square (4-cycle) bipartite:", is_bipartite(square))
print("triangle (3-cycle) bipartite:", is_bipartite(triangle))
```

```text
square (4-cycle) bipartite: True
triangle (3-cycle) bipartite: False
```

## 6. Planar graphs and Euler's formula

A graph is **planar** if it can be drawn with no crossing edges. For a connected planar graph: **V − E + F = 2** (F = faces, including the outer one). Consequences for simple planar graphs with V ≥ 3: **E ≤ 3V − 6**. So K₅ (V = 5, E = 10 > 9) is **not planar**; K₃,₃ isn't either (Kuratowski).

## 7. Graph colouring

Colour vertices so that adjacent ones differ. The minimum number of colours is the **chromatic number** χ(G).

| Graph | χ |
|---|---|
| tree (≥ 2 vertices), bipartite graph | 2 |
| odd cycle | 3 |
| Kₙ | n |
| any planar graph | ≤ 4 (Four Colour Theorem) |

Real use: **exam timetabling** (subjects = vertices, edge if a student takes both, colours = time slots), register allocation in compilers, frequency assignment.

## Common mistakes

- Confusing Euler (edges) with Hamiltonian (vertices).
- Forgetting the outer face in Euler's formula.
- Assuming a graph with n − 1 edges is a tree (it must also be connected / acyclic).
- Claiming "odd cycle ⇒ bipartite" (it's the opposite).

## Quick recap

- Σ deg(v) = 2|E|; the number of odd-degree vertices is even.
- Euler circuit ⇔ connected + all degrees even; Euler path ⇔ exactly 2 odd vertices. Hamiltonian: no easy test.
- Tree: connected, acyclic, n − 1 edges; Kₙ has nⁿ⁻² spanning trees.
- Bipartite ⇔ no odd cycle (2-colourable).
- Planar: V − E + F = 2, E ≤ 3V − 6; colouring: planar ≤ 4 colours.


Practice quiz and free certificate: https://skills101.in/learn/discrete-math/graph-theory-basics