# Graph Theory Workshop — Degree Sequences, Euler and Hamilton Paths, and Planarity Tests with Computed Examples

Source: https://skills101.in/learn/discrete-math/dm-graph-theory-degree-euler-hamilton-planar — Skills101 free tutorial (Discrete Mathematics). Updated 2026-11-18.

The [graph theory basics](https://skills101.in/learn/discrete-math/graph-theory-basics) lesson gave the definitions and the main theorems. This workshop uses them on real problems — the kind that appear as 5- and 10-mark questions: *"Is there a simple graph with degrees 3, 3, 3, 1?"*, *"Draw this figure without lifting your pen"*, *"Is this graph Hamiltonian?"*, *"Prove that this graph is not planar."* For each one we solve it by reasoning and then **compute** the answer in Python.

## 1. Degree sequences: can such a graph exist?

The **degree sequence** of a graph is the list of all vertex degrees, usually written largest first. A sequence is **graphical** if some **simple** graph (no loops, no repeated edges) has exactly those degrees.

Two quick tests rule many sequences out:

- The sum of degrees must be **even** (handshaking lemma).
- No degree can be more than n − 1, where n is the number of vertices.

Passing both is **not enough**. The **Havel–Hakimi** algorithm decides it exactly:

1. Sort the sequence in decreasing order and remove zeros.
2. Take the first degree d off the list.
3. Subtract 1 from each of the next d degrees. (The removed vertex is joined to the d vertices with the largest degrees.)
4. If any degree becomes negative, or there are fewer than d degrees left, the sequence is **not** graphical. If everything becomes 0, it **is** graphical. Otherwise repeat.

![Havel–Hakimi steps computed for two sequences: 3 3 2 2 2 reduces to 2 2 1 1, then 1 1 0, then 0 0, so it is graphical; 3 3 3 1 reduces to 2 2 0, then a vertex of degree 2 has only one other non-zero vertex to join, so it is not graphical even though its sum is even](https://skills101.in/learn-img/discrete-math/havel-hakimi.svg)

```python
def havel_hakimi(seq):
    seq = sorted(seq, reverse=True)
    print("start:", seq)
    while True:
        seq = [d for d in seq if d > 0]
        if not seq:
            return True
        d = seq.pop(0)
        if d > len(seq):
            return False
        for i in range(d):
            seq[i] -= 1
        if min(seq) < 0:
            print(f"take {d}:", seq, "<- negative")
            return False
        seq.sort(reverse=True)
        print(f"take {d}:", seq)

for s in [[3, 3, 2, 2, 2], [3, 3, 3, 1], [4, 4, 3, 1, 1]]:
    print("sum =", sum(s), "| graphical:", havel_hakimi(s))
    print()
```

```text
start: [3, 3, 2, 2, 2]
take 3: [2, 2, 1, 1]
take 2: [1, 1, 0]
take 1: [0]
sum = 12 | graphical: True

start: [3, 3, 3, 1]
take 3: [2, 2, 0]
sum = 10 | graphical: False

start: [4, 4, 3, 1, 1]
take 4: [3, 2, 0, 0]
sum = 13 | graphical: False
```

- `3 3 2 2 2` is graphical (for example, a 5-cycle with one extra chord).
- `3 3 3 1` has an even sum but is **not** graphical: three vertices of degree 3 in a 4-vertex graph must each touch every other vertex, so the last vertex would need degree 3, not 1.
- `4 4 3 1 1` fails immediately on the handshaking test (sum 13 is odd). Havel–Hakimi also rejects it.

**Two more facts that save time:**

- A **k-regular** graph (every vertex has degree k) on n vertices has n·k/2 edges. So a 3-regular graph on 7 vertices cannot exist (21/2 is not a whole number).
- In the **complement** of a simple graph (join exactly the pairs that were not joined), each degree d becomes n − 1 − d.

## 2. Euler paths: actually finding one

Recall the rule for a connected graph: an **Euler circuit** exists if every degree is even; an **Euler path** exists if exactly **two** vertices have odd degree, and it must start at one of them and end at the other.

Exams also ask you to **find** the path. **Hierholzer's algorithm** does it in O(E) time: walk along unused edges until you get stuck, then back up and splice in a detour from the last vertex that still has unused edges.

**Problem: draw the "house" without lifting your pen.** The house is a square A-B-C-D with both diagonals, plus a roof peak E joined to A and B.

```python
from collections import defaultdict

def euler_path(edges):
    adj = defaultdict(list)
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    odd = sorted(v for v in adj if len(adj[v]) % 2)
    print("degrees:", {v: len(adj[v]) for v in sorted(adj)}, "| odd:", odd)
    if len(odd) not in (0, 2):
        return None
    start = odd[0] if odd else sorted(adj)[0]
    used = [False] * len(edges)
    stack, path = [start], []
    while stack:
        u = stack[-1]
        while adj[u] and used[adj[u][-1][1]]:
            adj[u].pop()                      # drop edges already walked
        if adj[u]:
            v, i = adj[u].pop()
            used[i] = True
            stack.append(v)                   # walk forward
        else:
            path.append(stack.pop())          # stuck: this vertex is finished
    return path[::-1]

house = [("A", "B"), ("B", "C"), ("C", "D"), ("D", "A"), ("A", "C"), ("B", "D"), ("A", "E"), ("B", "E")]
route = euler_path(house)
print("route:", " -> ".join(route), "|", len(route) - 1, "edges")

konigsberg = [("A", "B"), ("A", "B"), ("A", "C"), ("A", "C"), ("A", "D"), ("B", "D"), ("C", "D")]
print("Konigsberg:", euler_path(konigsberg))
```

```text
degrees: {'A': 4, 'B': 4, 'C': 3, 'D': 3, 'E': 2} | odd: ['C', 'D']
route: C -> A -> E -> B -> D -> A -> B -> C -> D | 8 edges
degrees: {'A': 5, 'B': 3, 'C': 3, 'D': 3} | odd: ['A', 'B', 'C', 'D']
Konigsberg: None
```

![The house figure with the computed Euler path: the walk starts at C, the odd-degree corner, uses all 8 edges exactly once in the numbered order, and ends at the other odd corner D](https://skills101.in/learn-img/discrete-math/euler-house.svg)

Exactly two vertices (C and D) have odd degree, so the route must start at one and end at the other. The Königsberg bridges graph (multiple edges allowed) has **four** odd vertices, so the function returns `None`: no walk crosses each bridge exactly once.

## 3. Hamiltonian cycles: sufficient tests and their limits

There is no simple "if and only if" test for a **Hamiltonian cycle** (a cycle through every vertex exactly once). There are two well-known **sufficient** conditions for a simple graph with n ≥ 3 vertices:

| Theorem | Condition | Then |
|---|---|---|
| **Dirac** (1952) | every vertex has degree ≥ n/2 | Hamiltonian |
| **Ore** (1960) | deg(u) + deg(v) ≥ n for every pair of **non-adjacent** u, v | Hamiltonian |

"Sufficient" means: if the condition holds, a Hamiltonian cycle **definitely** exists. If it fails, you **learn nothing**. A plain 6-cycle fails both tests (every degree is 2 < 3) and is obviously Hamiltonian.

The famous counterexample in the other direction is the **Petersen graph**: 10 vertices, every degree 3, highly symmetric — and **no** Hamiltonian cycle. Since there is no shortcut test, we prove it by a complete backtracking search:

```python
def dirac(adj):
    n = len(adj)
    return all(len(adj[v]) >= n / 2 for v in adj)

def ore(adj):
    n = len(adj)
    return all(len(adj[u]) + len(adj[v]) >= n for u in adj for v in adj if u != v and v not in adj[u])

def hamiltonian_cycle(adj):
    vs = sorted(adj)
    n, start = len(vs), vs[0]
    path, seen = [start], {start}

    def extend():
        if len(path) == n:
            return start in adj[path[-1]]
        for w in sorted(adj[path[-1]]):
            if w not in seen:
                path.append(w); seen.add(w)
                if extend():
                    return True
                path.pop(); seen.discard(w)
        return False

    return path + [start] if extend() else None

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

c6 = graph([(i, (i + 1) % 6) for i in range(6)])
k33 = graph([(a, b) for a in "abc" for b in "xyz"])
petersen = graph([(i, (i + 1) % 5) for i in range(5)] +              # outer 5-cycle
                 [(5 + i, 5 + (i + 2) % 5) for i in range(5)] +      # inner star
                 [(i, i + 5) for i in range(5)])                     # spokes

for name, g in [("C6", c6), ("K3,3", k33), ("Petersen", petersen)]:
    print(f"{name:8} n={len(g):2}  Dirac={dirac(g)!s:5}  Ore={ore(g)!s:5}  cycle={hamiltonian_cycle(g)}")
```

```text
C6       n= 6  Dirac=False  Ore=False  cycle=[0, 1, 2, 3, 4, 5, 0]
K3,3     n= 6  Dirac=True   Ore=True   cycle=['a', 'x', 'b', 'y', 'c', 'z', 'a']
Petersen n=10  Dirac=False  Ore=False  cycle=None
```

- K₃,₃ satisfies Dirac (degree 3 ≥ 6/2), and the search finds a cycle, as the theorem promised.
- C₆ fails both tests but is Hamiltonian — the tests are one-way.
- The Petersen graph fails both tests, and the search tries every possibility and finds **no** cycle.

The search is exponential in the worst case. That is expected: deciding whether a graph is Hamiltonian is **NP-complete** (see the decidability lesson in Theory of Computation).

## 4. Proving a graph is not planar

For a **connected simple planar** graph with V ≥ 3 vertices, Euler's formula V − E + F = 2 leads to edge limits:

| Graph has… | Bound | Why |
|---|---|---|
| any simple planar graph | **E ≤ 3V − 6** | each face has at least 3 edges |
| no triangles (girth ≥ 4) | **E ≤ 2V − 4** | each face has at least 4 edges |
| shortest cycle length g | **E ≤ g(V − 2)/(g − 2)** | each face has at least g edges |

If a graph has **more** edges than the bound, it is **not planar**. If it is within the bound, the test says nothing — you then need a drawing (to show planar) or Kuratowski's theorem (to show non-planar).

```python
from collections import deque

def girth(adj):                  # length of the shortest cycle (BFS from every vertex)
    best = float("inf")
    for s in adj:
        dist, parent, q = {s: 0}, {s: None}, deque([s])
        while q:
            u = q.popleft()
            for w in adj[u]:
                if w not in dist:
                    dist[w], parent[w] = dist[u] + 1, u
                    q.append(w)
                elif parent[u] != w:
                    best = min(best, dist[u] + dist[w] + 1)
    return best

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, set()).add(v)
        adj.setdefault(v, set()).add(u)
    return adj

graphs = {
    "K4": graph([(a, b) for a in range(4) for b in range(a + 1, 4)]),
    "K5": graph([(a, b) for a in range(5) for b in range(a + 1, 5)]),
    "K3,3": graph([(a, b) for a in "abc" for b in "xyz"]),
    "cube Q3": graph([(a, a ^ (1 << k)) for a in range(8) for k in range(3) if a < a ^ (1 << k)]),
    "Petersen": graph([(i, (i + 1) % 5) for i in range(5)] + [(5 + i, 5 + (i + 2) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]),
}
for name, g in graphs.items():
    V, E, gi = len(g), sum(len(n) for n in g.values()) // 2, girth(g)
    bound = gi * (V - 2) / (gi - 2)
    verdict = "NOT planar" if E > bound else "bound passed (no conclusion)"
    print(f"{name:8} V={V:2} E={E:2} girth={gi}  bound={bound:5.2f}  -> {verdict}")
```

```text
K4       V= 4 E= 6 girth=3  bound= 6.00  -> bound passed (no conclusion)
K5       V= 5 E=10 girth=3  bound= 9.00  -> NOT planar
K3,3     V= 6 E= 9 girth=4  bound= 8.00  -> NOT planar
cube Q3  V= 8 E=12 girth=4  bound=12.00  -> bound passed (no conclusion)
Petersen V=10 E=15 girth=5  bound=13.33  -> NOT planar
```

- K₅ breaks E ≤ 3V − 6 (10 > 9) and K₃,₃ breaks E ≤ 2V − 4 (9 > 8): the two classic non-planar graphs.
- The Petersen graph has no cycle shorter than 5, so E ≤ 5(V − 2)/3 = 13.33, but it has 15 edges: **not planar**.
- K₄ and the cube pass their bounds. That alone proves nothing, but both can be drawn without crossings, so they are planar. For the cube, Euler's formula then gives F = 2 − V + E = 2 − 8 + 12 = **6 faces** — the six faces of a cube.

## Common mistakes

- Saying a sequence is graphical because its sum is even. Run Havel–Hakimi (3 3 3 1 has an even sum and is not graphical).
- Starting an Euler path at an even-degree vertex when two vertices are odd. It must start at an odd one.
- Treating Dirac or Ore as "if and only if". Failing them does **not** mean the graph is non-Hamiltonian.
- Using E ≤ 3V − 6 to prove a graph **is** planar. The bound can only prove non-planarity.
- Using E ≤ 3V − 6 for K₃,₃ (9 ≤ 12 passes). It has no triangles, so use E ≤ 2V − 4.

## Quick recap

- Degree sequences: even sum and max degree ≤ n − 1 are necessary; Havel–Hakimi decides exactly.
- k-regular on n vertices has nk/2 edges; complement degrees are n − 1 − d.
- Euler path: 0 or 2 odd vertices; find it with Hierholzer's algorithm in O(E), starting at an odd vertex.
- Dirac (deg ≥ n/2) and Ore (deg u + deg v ≥ n for non-adjacent pairs) guarantee a Hamiltonian cycle; the Petersen graph is 3-regular with none.
- Non-planarity: E > 3V − 6, or E > 2V − 4 without triangles, or E > g(V − 2)/(g − 2) in general.


Practice quiz and free certificate: https://skills101.in/learn/discrete-math/dm-graph-theory-degree-euler-hamilton-planar