Euler & Hamilton Circuits, Planar Graphs, Tree Traversals & Kruskal's MST

Explanation

Graph theory models discrete relational topologies across networks, dependencies, routing, and data structures. Tree structures provide unique paths between any pair of vertices. Kruskal's and Prim's greedy strategies guarantee optimal minimum spanning trees by exploiting the cut property of weighted undirected graphs.

Key points

• Euler Circuit: Traverses every EDGE exactly once and returns to start. Exists iff graph is connected and EVERY vertex has an EVEN degree.
• Hamilton Circuit: Visits every VERTEX exactly once and returns to start (NP-complete in general). Dirac's Theorem: If |V| ≥ 3 and deg(v) ≥ |V|/2 for all v, G has a Hamilton circuit.
• Planar Graphs: Can be drawn in a plane without intersecting edges. Euler's Formula: V - E + R = 2. For simple planar graphs with |V| ≥ 3: E ≤ 3V - 6.
• Trees: Connected acyclic graphs. A tree with n vertices contains exactly n - 1 edges.
• Minimum Spanning Tree (MST): Kruskal's greedy algorithm sorts edges by weight and iteratively adds the cheapest edge that does not form a cycle (using Disjoint Set Union / DSU).

Example

Code examples

// Kruskal's Minimum Spanning Tree Algorithm in C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge { int u, v, weight; };

struct DSU {
    vector<int> parent;
    DSU(int n) : parent(n) { for (int i = 0; i < n; i++) parent[i] = i; }
    int find(int i) { return (parent[i] == i) ? i : (parent[i] = find(parent[i])); }
    bool unite(int i, int j) {
        int rootI = find(i), rootJ = find(j);
        if (rootI != rootJ) { parent[rootI] = rootJ; return true; }
        return false;
    }
};

int kruskalMST(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(), [](Edge a, Edge b) { return a.weight < b.weight; });
    DSU dsu(n);
    int mstCost = 0, edgesCount = 0;
    for (const auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            mstCost += e.weight;
            if (++edgesCount == n - 1) break;
        }
    }
    return mstCost;
}

Exam questions

• [8 Marks] State Euler's formula for connected planar graphs and prove it using mathematical induction. Show that K_{3,3} is non-planar.
• [8 Marks] State the necessary and sufficient conditions for a connected graph to contain an Euler circuit. Differentiate between Euler path and Hamilton path with examples.
• [7 Marks] Apply Kruskal's algorithm to find the Minimum Spanning Tree (MST) of a given 6-vertex weighted graph and calculate total weight.