Part 4: What Is a Graph? Types, Families & Representations

The Formal Definition of a Graph

A graph is a pair \(G = (V, E)\), where \(V\) is a set of vertices (or nodes) and \(E\) is a set of edges, each edge being an unordered pair \(\{u, v\}\) of vertices for an undirected graph (or an ordered pair \((u,v)\) for a directed graph, also called a digraph). If \(e = \{u, v\} \in E\), we say \(e\) is incident to \(u\) and \(v\), and that \(u\) and \(v\) are adjacent (neighbors).

Directed, Weighted, Simple, and Multigraphs

In a digraph, a vertex \(v\) with in-degree 0 is a source; one with out-degree 0 is a sink. An isolated vertex with both in-degree and out-degree 0 is an isolated node, while a vertex adjacent to every other vertex in an undirected graph is a universal vertex (or dominant vertex). These show up constantly once we study directed acyclic graphs (DAGs) in Part 7 and network flow in Part 14.

Walks, Trails, Paths & Cycles

These terms are easy to conflate, but the exact structural restrictions on repeated vertices or edges matter for major theorems (e.g., Eulerian circuits require closed trails; Hamiltonian cycles require simple paths; network flow relies on augmenting paths):

• Walk: any sequence of vertices \(v_0, v_1, \dots, v_k\) where consecutive vertices are adjacent. Vertices and edges may repeat freely.
• Closed walk: a walk that starts and ends at the same vertex (\(v_0 = v_k\)).
• Open walk: a walk that starts and ends at different vertices (\(v_0 \neq v_k\)).
• Trail: a walk with no repeated edge (vertices may still repeat).
• Circuit: a closed trail (no repeated edges, but starts and ends at the same vertex).
• Eulerian trail: a trail that visits every edge of the graph exactly once.
• Eulerian circuit: a closed trail (circuit) that visits every edge of the graph conditions-free and returns to the start.
• Path (simple path): a walk with no repeated vertex (and hence no repeated edge either).
• Hamiltonian path: a simple path that visits every vertex of the graph exactly once.
• Cycle: a closed path — no repeated vertices except that the first vertex equals the last (\(v_0 = v_k\)).
• Hamiltonian cycle: a closed path (cycle) that visits every vertex of the graph exactly once and returns to the start.
• Girth: the length of the shortest cycle in a graph (defined as \(\infty\) if the graph has no cycles).
• Circumference: the length of the longest cycle in a graph.
• Distance \(d(u,v)\): the length (number of edges) of the shortest path connecting \(u\) and \(v\).
• Diameter: the maximum distance \(d(u,v)\) over all connected pairs of vertices in a graph.
• Radius: the minimum eccentricity among all vertices (where eccentricity is a vertex's max distance to any other vertex).

Graph Families

A handful of named graph families reappear throughout the entire series as building blocks, extremal examples, and counterexamples.

Bipartite Graphs and Trees

Degree Theory & the Handshaking Lemma

The degree \(\deg(v)\) of a vertex is the number of edges incident to it (a self-loop, in a pseudograph, counts twice). The sequence of all vertex degrees, usually sorted, is the degree sequence.

$$\textbf{Handshaking Lemma: } \sum_{v \in V} \deg(v) = 2|E|$$

We proved this by double counting in Part 2, and by contradiction (the odd-degree-count corollary) in Part 1. A natural follow-up question: given a sequence of non-negative integers, does some simple graph realize it as a degree sequence? The Erdős–Gallai theorem answers this in general, and the constructive Havel-Hakimi algorithm answers it by actually building such a graph (or proving none exists) — we implement Havel-Hakimi as part of the algorithm deep dives once the batch reaches it.

Subgraphs & Graph Operations

A subgraph \(H\) of \(G\) has \(V(H) \subseteq V(G)\) and \(E(H) \subseteq E(G)\) (with every edge's endpoints still in \(V(H)\)). Two important special cases: an induced subgraph on vertex set \(S \subseteq V\) includes every edge of \(G\) with both endpoints in \(S\); a spanning subgraph keeps all of \(V(G)\) but only some edges. The complement \(\overline{G}\) has the same vertex set with edges exactly where \(G\) has non-edges — a direct application of set complements from Part 1.

Graph Representations

How a graph lives in memory determines an algorithm's complexity. The two workhorse representations:

Adjacency list — a map from each vertex to the list of its neighbors. Space: \(O(V+E)\). Best for sparse graphs and for iterating a vertex's neighbors quickly (most graph algorithms in this series, starting with BFS/DFS in Parts 5–6, use this).

Adjacency matrix — an \(n \times n\) matrix \(A\) with \(A_{ij} = 1\) (or the edge weight) if \(\{i,j\} \in E\). Space: \(O(V^2)\) regardless of edge count, but \(O(1)\) edge-existence checks — ideal for dense graphs and algorithms like Floyd-Warshall (Part 10) that scan all pairs anyway.

from collections import defaultdict

class Graph:
    """Adjacency-list graph. Space: O(V + E)."""

    def __init__(self, directed=False):
        self.adj = defaultdict(list)
        self.directed = directed

    def add_edge(self, u, v, weight=1):
        self.adj[u].append((v, weight))
        if not self.directed:
            self.adj[v].append((u, weight))

    def neighbors(self, u):
        return self.adj[u]

    def degree(self, u):
        return len(self.adj[u])

# Build the 4-cycle A-B-C-D-A
g = Graph(directed=False)
for u, v in [("A", "B"), ("B", "C"), ("C", "D"), ("D", "A")]:
    g.add_edge(u, v)

print("Neighbors of A:", g.neighbors("A"))   # [('B', 1), ('D', 1)]
print("Degree of A:", g.degree("A"))          # 2

# Handshaking Lemma check: sum(deg(v)) == 2 * |E|
total_degree = sum(g.degree(v) for v in "ABCD")
print("Sum of degrees:", total_degree, "== 2 * 4 edges =", 2 * 4)

#include <vector>
#include <unordered_map>
#include <iostream>
using namespace std;

class Graph {
    unordered_map<string, vector<pair<string, int>>> adj;
    bool directed;
public:
    Graph(bool isDirected = false) : directed(isDirected) {}

    void addEdge(const string& u, const string& v, int weight = 1) {
        adj[u].push_back({v, weight});
        if (!directed) adj[v].push_back({u, weight});
    }

    vector<pair<string, int>>& neighbors(const string& u) {
        return adj[u];
    }

    int degree(const string& u) {
        return adj[u].size();
    }
};

int main() {
    Graph g(false);
    g.addEdge("A", "B");
    g.addEdge("B", "C");
    g.addEdge("C", "D");
    g.addEdge("D", "A");

    cout << "Degree of A: " << g.degree("A") << endl; // 2

    int totalDegree = 0;
    for (char v : {'A', 'B', 'C', 'D'})
        totalDegree += g.degree(string(1, v));
    cout << "Sum of degrees: " << totalDegree << " == 2 * 4 edges" << endl;
    return 0;
}

import java.util.*;

class Graph {
    private Map<String, List<int[]>> adjIndex = new HashMap<>();
    private Map<String, List<Map.Entry<String, Integer>>> adj = new HashMap<>();
    private boolean directed;

    public Graph(boolean directed) { this.directed = directed; }

    public void addEdge(String u, String v, int weight) {
        adj.computeIfAbsent(u, k -> new ArrayList<>())
           .add(new AbstractMap.SimpleEntry<>(v, weight));
        if (!directed) {
            adj.computeIfAbsent(v, k -> new ArrayList<>())
               .add(new AbstractMap.SimpleEntry<>(u, weight));
        }
    }

    public void addEdge(String u, String v) { addEdge(u, v, 1); }

    public List<Map.Entry<String, Integer>> neighbors(String u) {
        return adj.getOrDefault(u, new ArrayList<>());
    }

    public int degree(String u) { return neighbors(u).size(); }

    public static void main(String[] args) {
        Graph g = new Graph(false);
        g.addEdge("A", "B");
        g.addEdge("B", "C");
        g.addEdge("C", "D");
        g.addEdge("D", "A");

        System.out.println("Degree of A: " + g.degree("A")); // 2

        int totalDegree = 0;
        for (String v : new String[]{"A", "B", "C", "D"})
            totalDegree += g.degree(v);
        System.out.println("Sum of degrees: " + totalDegree + " == 2 * 4 edges");
    }
}

Edge List, Incidence Matrix, and CSR

Three more representations matter in specific contexts:

• Edge list: just a flat list of \((u, v, w)\) triples. Space \(O(E)\). Ideal input format for Kruskal's algorithm (Part 11), which sorts edges globally by weight.
• Incidence matrix: an \(|V| \times |E|\) matrix where entry \((v, e)\) is nonzero iff vertex \(v\) is an endpoint of edge \(e\). This is the matrix whose column space underlies the cut space from Part 3.
• Compressed Sparse Row (CSR): the production-grade format for huge sparse graphs — a flat array of all neighbors (concatenated) plus an offset array marking where each vertex's neighbor block starts. This avoids the pointer-chasing overhead of a Python-style adjacency list and is what high-performance graph libraries (and GPUs) actually use internally.

Exercises

1. Draw \(K_5\), \(C_5\), and \(K_{2,3}\). Verify \(|E(K_5)| = \binom{5}{2} = 10\).
2. Give an example of a walk that is not a trail, a trail that is not a path, and explain why every path is automatically a trail.
3. Prove that a graph is bipartite if it is a tree (hint: 2-color the tree using BFS layers, then show adjacent vertices always land in different layers — you can take this on faith for now; we prove it rigorously in Part 5).
4. Write out the degree sequence of \(K_{3,3}\), and verify the Handshaking Lemma holds.
5. Challenge: Implement the adjacency-matrix representation in your language of choice, and write a function that converts it to an adjacency list in \(O(V^2)\) time. Then argue why converting the other direction (list → matrix) is also \(O(V^2)\), even though the list itself only takes \(O(V+E)\) space.

Conclusion & Next Steps

Graph theory now has its formal footing: the definition of \(G = (V,E)\), the walk/trail/path/cycle hierarchy, the major named graph families, degree theory and the Handshaking Lemma, subgraphs and basic operations, and every representation you'll implement algorithms against. Everything from here on is genuinely about graphs.