Part 3

15 min read18 headingsSplit lesson page

Lesson overview | Previous part | Lesson overview

Graph Basics: Part 11: Common Mistakes to Appendix C: Common Graph Families - Properties at a Glance

11. Common Mistakes

#	Mistake	Why It's Wrong	Fix
1	Confusing "path" and "walk"	A walk allows vertex repetition; a path does not. Claiming a walk is a path overstates the constraint.	Use "walk" for general traversals, "path" only when no vertex is repeated.
2	Assuming all graphs are simple	Real-world graphs often have self-loops (user follows self) or parallel edges (multiple bus routes). GCN explicitly adds self-loops.	State "simple graph" explicitly when assuming no self-loops or parallel edges.
3	Forgetting that edges in undirected graphs are unordered	Writing $(u,v)$ for undirected edges suggests direction. $\{u,v\} = \{v,u\}$ but $(u,v) \neq (v,u)$ .	Use $\{u,v\}$ for undirected, $(u,v)$ for directed.
4	Claiming degree sequence determines the graph	Many non-isomorphic graphs share the same degree sequence. Example: $C_6$ and $K_{3,3} \setminus M$ (perfect matching removed).	Degree sequence is a necessary but not sufficient invariant for isomorphism.
5	Assuming bipartite $\iff$ 2-colorable	These are actually equivalent! The common mistake is failing to recognise this equivalence and testing bipartiteness separately from 2-coloring.	Bipartite $\Leftrightarrow$ no odd cycle $\Leftrightarrow$ $\chi(G) \leq 2$ . Use BFS 2-coloring to test bipartiteness.
6	Confusing "connected" with "strongly connected" for digraphs	A weakly connected digraph may have vertex pairs with no directed path between them. Strong connectivity requires directed paths in both directions.	Always specify "weakly" or "strongly" for directed graphs.
7	Treating graph complement as "flipping edges"	The complement removes existing edges AND adds all missing edges. It's not "toggle each edge" unless you mean exactly that (which IS the complement).	$\bar{G}$ has edge $\{u,v\}$ iff $G$ does NOT have edge $\{u,v\}$ .
8	Assuming GNNs can distinguish any two non-isomorphic graphs	Message-passing GNNs are bounded by 1-WL. They fail on regular graphs of the same degree and many other cases.	Use 1-WL as the upper bound. For tasks requiring more power, consider higher-order GNNs or graph transformers.
9	Counting edges in $K_n$ as $n^2$	$K_n$ has $\binom{n}{2} = n(n-1)/2$ edges, not $n^2$ . The adjacency matrix has $n^2$ entries but is symmetric with zero diagonal.	Use the formula $\binom{n}{2}$ for undirected, $n(n-1)$ for directed complete graphs.
10	Forgetting the handshaking lemma when debugging graph code	If your computed degree sum is odd, the graph is invalid - odd degree sums are impossible.	Always verify $\sum \deg(v) = 2

12. Exercises

Exercise 1 * - Handshaking Lemma Verification

Construct three specific graphs (your choice of vertex/edge sets) and verify the handshaking lemma $\sum \deg(v) = 2|E|$ for each. (a) A graph with 5 vertices and 7 edges. (b) A directed graph with 4 vertices - verify $\sum \deg^+ = \sum \deg^- = |E|$ . (c) A bipartite graph $K_{3,4}$ - compute degrees of both sides.

Exercise 2 * - Degree Sequences and Graphicality

(a) Determine whether each sequence is graphic (can be realised as a simple graph): $(4, 3, 3, 2, 2)$ , $(3, 3, 3, 1)$ , $(5, 3, 2, 2, 2, 2)$ . (b) For each graphic sequence, construct a graph that realises it. (c) Implement the Erdos-Gallai test programmatically.

Exercise 3 * - Paths, Cycles, and Distance

Given the Petersen graph (look up its edge list): (a) Find all shortest paths from vertex 0 to vertex 5. (b) Compute the diameter and radius. (c) Verify the girth is 5 by finding a shortest cycle. (d) Show that the Petersen graph has no Hamiltonian cycle (explain why, or try exhaustive search).

Exercise 4 ** - Tree Equivalences

(a) Prove that if $G$ is connected and has exactly $n - 1$ edges, then $G$ is acyclic. (b) Prove that in a tree, there is exactly one path between every pair of vertices. (c) Compute the number of spanning trees of $K_4$ using Kirchhoff's matrix tree theorem ( $\det$ of any cofactor of $L$ ) and verify against Cayley's formula $4^{4-2} = 16$ .

Exercise 5 ** - Bipartiteness Testing

(a) Implement a BFS-based algorithm to test whether a graph is bipartite. (b) If bipartite, output the bipartition $(U, W)$ . (c) If not bipartite, output an odd cycle as a certificate. (d) Test on: $C_6$ (bipartite), $C_7$ (not bipartite), Petersen (not bipartite), $K_{3,3}$ (bipartite).

Exercise 6 ** - Graph Distance and Eccentricity

(a) Compute the all-pairs shortest path distance matrix for a given graph using BFS. (b) From the distance matrix, compute eccentricity, diameter, radius, and center. (c) Verify: for any connected graph, $\operatorname{rad}(G) \leq \operatorname{diam}(G) \leq 2 \cdot \operatorname{rad}(G)$ .

Exercise 7 *** - Weisfeiler-Leman Test and GNN Expressiveness

(a) Implement the 1-WL color refinement algorithm. (b) Run it on two non-isomorphic 3-regular graphs on 6 vertices. Does 1-WL distinguish them? (c) Construct a pair of non-isomorphic graphs that 1-WL CANNOT distinguish (hint: use two regular graphs with the same degree sequence and spectrum). (d) Explain why this means a standard message-passing GNN cannot distinguish them either.

Exercise 8 *** - Real-World Graph Analysis

Model a real-world system as a graph and analyse it: (a) Choose a domain: social network (use Zachary's karate club), citation network, molecular graph, or small knowledge graph. (b) Compute: number of vertices/edges, degree distribution, diameter, connected components, clustering coefficient. (c) Test whether the graph is bipartite, planar, or has any special structure. (d) Discuss: what would a 2-layer GNN "see" on this graph? Which pairs of vertices can exchange information?

13. Why This Matters for AI (2026 Perspective)

Concept	AI Impact
Graph definition $G = (V, E)$	The foundational data structure for GNNs, knowledge graphs, and computation graphs in all major frameworks (PyTorch Geometric, DGL, JAX-based graph libraries)
Directed graphs	Computation graphs (autograd DAGs), causal graphs (structural causal models), citation networks, dependency parse trees
Weighted graphs	Attention weights in transformers define weighted digraphs; similarity graphs ( $k$ -NN) use distance weights; Markov chains use transition probabilities
Degree and degree distribution	Determines GNN aggregation balance; power-law distributions cause over-squashing; degree-based normalisation ( $D^{-1/2}AD^{-1/2}$ ) is standard in GCN
Paths and distance	GNN receptive field is bounded by path length; graph diameter determines minimum GNN depth; shortest-path features improve GNN expressiveness
Connectivity	Disconnected components are processed independently by message-passing GNNs; virtual nodes connect components artificially
Trees and DAGs	Decision trees (XGBoost), parse trees (NLP), computation graphs (autograd), Bayesian networks, causal DAGs
Bipartite graphs	User-item recommendation (matrix factorization), bipartite matching (assignment), entity-relation graphs
Graph isomorphism	GNN permutation invariance; graph-level classification requires isomorphism-invariant readout functions
Weisfeiler-Leman test	Provable upper bound on message-passing GNN expressiveness (Xu et al., 2019); drives research into more expressive architectures (Graph Transformers, subgraph GNNs)
Graph coloring	Scheduling, resource allocation, register allocation in compilers; CSP solving with neural methods
Hypergraphs	Higher-order attention (multi-head attention as learned hyperedges); set function learning (DeepSets); group interaction modeling
Planar graphs	Geographic ML, mesh-based physics simulations (weather prediction, fluid dynamics with GNNs)

14. Conceptual Bridge

Looking Back

This section builds on the mathematical foundations established in earlier chapters:

Sets and functions (Ch. 01) provide the language for defining vertex sets, edge sets, and the mappings (isomorphisms, colourings) between them
Matrix operations (Ch. 02) connect through the adjacency matrix $A$ - the handshaking lemma is $\mathbf{1}^\top A \mathbf{1} = 2|E|$ , and walk counting uses matrix powers $A^k$
Eigenvalues (Ch. 03) will become central in the next section - the spectrum of $A$ and $L$ encodes deep structural information about the graph

Looking Forward

The vocabulary and theory developed here is the foundation for the rest of the Graph Theory chapter:

02 Graph Representations takes the abstract objects defined here (adjacency, degree, connectivity) and asks: how do we store them in memory?
03 Graph Algorithms provides efficient algorithms for computing the properties defined here: BFS for distance, DFS for connectivity, Dijkstra for weighted shortest paths
04 Spectral Graph Theory analyses the eigenvalues of $A$ , $D$ , and $L$ - connecting the combinatorial properties (connectivity, bipartiteness, clustering) to algebraic properties (spectrum)
05 Graph Neural Networks builds learnable functions on graphs, with the message-passing paradigm directly implementing walk-based aggregation on the structures defined here
06 Random Graphs asks: what happens when edges are drawn randomly? The degree sequences, connectivity thresholds, and component structure we defined here become probabilistic phenomena

The Big Picture

GRAPH BASICS IN THE CURRICULUM
========================================================================

  Ch.01 Sets & Logic -----------> Vertex sets, edge sets, mappings
           |
  Ch.02 Linear Algebra ---------> Adjacency matrix, degree matrix
           |
           v
  +---------------------------------------------------------+
  |                  01 GRAPH BASICS                        |
  |   Definitions * Degree * Paths * Connectivity * Trees    |
  |   Bipartite * Coloring * Isomorphism * WL Test           |
  +-------+-----------+-----------+-----------+-------------+
          |           |           |           |
          v           v           v           v
       02          03        04         05
    Represent.   Algorithms   Spectral     GNNs
    (storage)   (BFS, DFS)  (eigenvals)  (learning)
                                           |
                                           v
                                    06 Random Graphs
                                    (probabilistic)

========================================================================

15. Quick Computational Reference

The table below collects the key formulas and algorithms from this section for fast lookup during implementation.

15.1 Degree and Edge Counting

Quantity	Formula	Python (NetworkX)
Total edges	$m = \tfrac{1}{2}\sum_v \deg(v)$	`G.number_of_edges()`
Max degree	$\Delta(G) = \max_v \deg(v)$	`max(d for _,d in G.degree())`
Min degree	$\delta(G) = \min_v \deg(v)$	`min(d for _,d in G.degree())`
Average degree	$\bar{d} = 2m/n$	`2*G.number_of_edges()/G.number_of_nodes()`
Degree sequence	Sorted list of degrees	`sorted([d for _,d in G.degree()], reverse=True)`

15.2 Adjacency Matrix Operations

Operation	Matrix expression	Interpretation
Degree of $v_i$	$(A\mathbf{1})_i$	Row sum
Number of walks of length $k$	$(A^k)_{ij}$	Matrix power
Number of triangles	$\tfrac{1}{6}\operatorname{tr}(A^3)$	Trace of cube
Graph Laplacian	$L = D - A$	$D = \operatorname{diag}(A\mathbf{1})$
Normalised Laplacian	$L_{\text{sym}} = I - D^{-1/2}AD^{-1/2}$	Eigenvalues in $[0, 2]$

15.3 Graph Properties - Decision Table

Property	Algorithm	Time complexity
Connectivity	BFS/DFS from any vertex	$O(n + m)$
Strong connectivity	Kosaraju or Tarjan	$O(n + m)$
Bipartiteness	BFS 2-colouring	$O(n + m)$
Euler circuit	Check all degrees even + connected	$O(n + m)$
Spanning tree	BFS/DFS tree	$O(n + m)$
Minimum spanning tree	Kruskal or Prim	$O(m \log n)$
Shortest path (unweighted)	BFS	$O(n + m)$
Shortest path (weighted)	Dijkstra (non-negative)	$O((n+m)\log n)$
Topological sort (DAG)	Kahn's algorithm	$O(n + m)$
Planarity test	Boyer-Myrvold	$O(n)$

15.4 Graph Invariant Checklist

When you need to test whether two graphs $G_1, G_2$ might be isomorphic, check these invariants in order from cheapest to most expensive:

$|V|$ equal? (O(1))
$|E|$ equal? (O(1))
Degree sequences equal? (O(n log n))
Degree distribution equal? (O(n))
Number of triangles equal? (O(n^3) or O(n^{2.37}) with fast matrix multiply)
Characteristic polynomial of $A$ equal? (O(n^3))
Chromatic polynomial equal? (#P-hard in general)
Run VF2 or Nauty for exact isomorphism check.

If any invariant differs, the graphs are definitively not isomorphic. If all agree, they are likely isomorphic but not guaranteed (cospectral non-isomorphic graphs exist).

Implementation note. In practice, NetworkX provides nx.is_isomorphic(G1, G2) using VF2, and nx.graph_atlas_g() for enumeration. For large graphs ($n > 10^4$), use approximate fingerprinting (degree sequence + triangle count + eigenvalue moments) before exact checks.

16. Section Summary

This section covered the full vocabulary of graph theory needed to read modern GNN papers and implement graph algorithms from scratch.

Core objects defined:

A graph $G = (V, E)$ is a pair of a vertex set and an edge set; variants include directed, weighted, simple, multi, and hypergraphs.
The degree of a vertex counts its incident edges; the handshaking lemma $\sum \deg(v) = 2|E|$ is the universal sanity check.
Walks, trails, paths, and cycles form a hierarchy of traversal objects; Eulerian and Hamiltonian structures live at opposite ends of algorithmic tractability.

Core structural theorems:

Connectivity is characterised by BFS/DFS reachability; bridges and articulation points are the fragile points; Menger's theorem equates disjoint paths with cuts.
Trees admit six equivalent definitions and are the minimum connected structures; spanning trees compress any connected graph.
Bipartite graphs are exactly those with no odd cycles, equivalent to 2-colourability, and support Konig's matching theorem.
Planar graphs satisfy Euler's formula $n - m + f = 2$ and are characterised by Kuratowski's forbidden minors.

Core AI connections:

The Weisfeiler-Leman test (1-WL) is the provable upper bound on the expressiveness of all message-passing GNNs, showing that structural indistinguishability in WL implies indistinguishability by GNNs.
Graph motifs (triangles, stars, paths) are the structural units that standard GNNs cannot count, motivating expressiveness research.
Graph isomorphism, automorphisms, and invariants formalise what it means for a graph function to be permutation-invariant - the foundational requirement for graph-level prediction.

The theory notebook works through all matrix computations, proofs, and visualisations in executable Python. The exercises notebook provides graded practice from basic degree calculations to proving WL indistinguishability of specific graph pairs.

The single most important takeaway: graphs are simultaneously combinatorial objects (studied via degree, paths, cycles), algebraic objects (studied via matrices and polynomials), and computational objects (studied via algorithms and complexity). GNNs sit at the intersection of all three perspectives - they are learned functions that respect the algebraic symmetries of graphs while computing efficiently on the combinatorial structure. Every concept in this section reappears in that context.

17. Further Reading

Foundational Texts

Diestel, R. Graph Theory (5th ed., 2017) - The standard graduate reference. Free PDF at diestel-graph-theory.com. Chapters 1-2 cover the material in this section with full proofs.
West, D. Introduction to Graph Theory (2nd ed., 2001) - Excellent undergraduate text with many exercises. Chapters 1 (Fundamental Concepts) and 2 (Trees and Distance) map directly to 01.
Bondy, J. A. and Murty, U. S. R. Graph Theory (2008, Springer GTM) - Comprehensive coverage including extremal graph theory and Ramsey theory.

For the AI/ML Connection

Hamilton, W. L. Graph Representation Learning (2020, Synthesis Lectures) - The definitive ML-focused introduction. Chapter 2 covers graph basics from an ML perspective. Free draft at cs.mcgill.ca/~wlh/grl_book/.
Xu, K. et al. "How Powerful are Graph Neural Networks?" ICLR 2019 - Establishes the 1-WL upper bound on message-passing GNNs. Essential reading before implementing GNNs.
Bronstein, M. et al. "Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges" arXiv 2021 - Places graphs in the broader context of geometric priors in ML (symmetry, equivariance).

Historical Papers

Euler, L. "Solutio problematis ad geometriam situs pertinentis" (1736) - The Konigsberg bridges paper: the first graph theory result.
Erdos, P. and Renyi, A. "On Random Graphs I" Publicationes Mathematicae (1959) - Founding paper of random graph theory; introduces the $G(n,p)$ model studied in 06.
Appel, K. and Haken, W. "Every planar map is four colorable" Illinois J. Math. (1977) - The first major computer-assisted proof in mathematics.

<- Back to Graph Theory | Next: Graph Representations ->

Appendix A: Graph Theory Notation Reference

A quick-reference table for the notation used throughout this section and the rest of the chapter.

A.1 Graph Notation

Symbol	Meaning
$G = (V, E)$	Graph with vertex set $V$ and edge set $E$
$n = \lvert V \rvert$	Order (number of vertices)
$m = \lvert E \rvert$	Size (number of edges)
$u \sim v$	Vertices $u$ and $v$ are adjacent
$\mathcal{N}(v)$	Neighbourhood of $v$ : all vertices adjacent to $v$
$\mathcal{N}[v]$	Closed neighbourhood: $\mathcal{N}(v) \cup \{v\}$
$\deg(v)$	Degree of vertex $v$ in an undirected graph
$\deg^+(v)$	Out-degree of $v$ in a digraph
$\deg^-(v)$	In-degree of $v$ in a digraph
$\delta(G)$	Minimum degree: $\min_{v \in V}\deg(v)$
$\Delta(G)$	Maximum degree: $\max_{v \in V}\deg(v)$
$d(u, v)$	Graph distance (shortest path length) from $u$ to $v$
$\operatorname{diam}(G)$	Diameter: $\max_{u,v} d(u,v)$
$\operatorname{rad}(G)$	Radius: $\min_v \max_u d(u,v)$
$\chi(G)$	Chromatic number
$\kappa(G)$	Vertex connectivity
$\lambda(G)$	Edge connectivity
$G[S]$	Induced subgraph on vertex subset $S$
$G - v$	Graph with vertex $v$ and its incident edges removed
$G - e$	Graph with edge $e$ removed
$G / e$	Graph with edge $e$ contracted
$\bar{G}$	Complement of $G$
$L(G)$	Line graph of $G$
$\operatorname{Aut}(G)$	Automorphism group of $G$

A.2 Special Graph Families

Symbol	Name	Definition
$K_n$	Complete graph	$n$ vertices, all $\binom{n}{2}$ edges
$K_{m,n}$	Complete bipartite	$m + n$ vertices, $mn$ edges in bipartite form
$C_n$	Cycle	$n$ vertices in a single cycle
$P_n$	Path	$n$ vertices in a single path
$\bar{K}_n$	Empty graph	$n$ vertices, no edges
$S_n$	Star	One center vertex connected to $n-1$ leaves
$W_n$	Wheel	$C_n$ plus one central vertex connected to all
$Q_n$	Hypercube	$2^n$ vertices, $n$ -bit binary strings as vertices

A.3 Graph Matrices

Matrix	Symbol	Definition	Size
Adjacency	$A$	$A_{ij} = 1$ if $\{i,j\} \in E$	$n \times n$
Degree	$D$	$D = \operatorname{diag}(\deg(v_1), \ldots, \deg(v_n))$	$n \times n$ diagonal
Laplacian	$L$	$L = D - A$	$n \times n$
Normalised Laplacian	$L_{\text{sym}}$	$I - D^{-1/2}AD^{-1/2}$	$n \times n$
Incidence	$B$	$B_{ve} = 1$ if $v \in e$ (undirected)	$n \times m$
Distance	$\mathcal{D}$	$\mathcal{D}_{ij} = d(v_i, v_j)$	$n \times n$

Appendix B: Key Theorems Summary

Theorem	Statement	Significance
Handshaking Lemma	$\sum_{v}\deg(v) = 2\lvert E \rvert$	Fundamental constraint; useful for validation
Euler's Theorem	Eulerian circuit $\iff$ all degrees even	First theorem of graph theory (1736)
Odd-Cycle Theorem	Bipartite $\iff$ no odd cycles	Connects structure to coloring
Tree Equivalences	6 equivalent definitions of a tree	Foundational for spanning trees
Cayley's Formula	$n^{n-2}$ spanning trees in $K_n$	Counts labeled trees
Matrix Tree Theorem	Spanning trees = any cofactor of $L$	Connects combinatorics to linear algebra
Euler's Planar Formula	$n - m + f = 2$	Topological constraint on planar graphs
Kuratowski's Theorem	Planar $\iff$ no $K_5$ or $K_{3,3}$ subdivision	Characterises planarity
Four Color Theorem	$\chi(G) \leq 4$ for planar $G$	Computer-assisted proof (1976/2008)
Brooks' Theorem	$\chi(G) \leq \Delta(G)$ (non-complete, non-odd-cycle)	Upper bound on chromatic number
Konig's Theorem	Max matching = min vertex cover (bipartite)	Foundation of bipartite combinatorics
Menger's Theorem	Max disjoint paths = min cut	Max-flow min-cut for graphs
WL-GNN Equivalence	MPNN power $\leq$ 1-WL test (Xu et al., 2019)	Expressiveness bound for GNNs
Robertson-Seymour	Every minor-closed property has finite forbidden set	Deepest result in structural graph theory

Appendix C: Common Graph Families - Properties at a Glance

Graph	$n$	$m$	Regular?	Bipartite?	Planar?	$\chi$	Diameter
$K_n$	$n$	$n(n{-}1)/2$	$(n{-}1)$ -reg	$n \leq 2$	$n \leq 4$	$n$	$1$
$K_{n,n}$	$2n$	$n^2$	$n$ -reg	Yes	$n \leq 2$	$2$	$2$
$C_n$	$n$	$n$	$2$ -reg	$n$ even	Yes	$\lfloor n/2 \rfloor$	$\lfloor n/2 \rfloor$
$P_n$	$n$	$n{-}1$	No	Yes	Yes	$2$	$n{-}1$
Tree (any)	$n$	$n{-}1$	No (gen.)	Yes	Yes	$2$	$\leq n{-}1$
Petersen	$10$	$15$	$3$ -reg	No	No	$3$	$2$
$Q_n$ (hypercube)	$2^n$	$n2^{n-1}$	$n$ -reg	Yes	$n \leq 3$	$2$	$n$

Graph Basics: Part 3 - Common Mistakes To Appendix C Common Graph Families Properties At A