Graph Theory

ACSL graph theory problems give you a graph (a set of nodes connected by edges) and ask you to compute properties like degree, shortest path, or minimum spanning tree. The graphs are small enough to solve by hand - usually 5-8 nodes. The challenge is applying the right algorithm quickly and not missing an edge.

Terminology you must know

Vertex (node): a point in the graph
Edge: a connection between two vertices
Directed graph (digraph): edges have direction (arrows). An edge from A to B does not mean there is one from B to A.
Undirected graph: edges go both ways. An edge between A and B means you can go either direction.
Weighted graph: each edge has a numerical cost/distance
Degree: the number of edges connected to a vertex. In a directed graph, in-degree counts incoming edges and out-degree counts outgoing edges.
Path: a sequence of vertices connected by edges
Cycle: a path that starts and ends at the same vertex
Connected graph: every vertex can reach every other vertex (undirected)
Tree: a connected graph with no cycles. A tree with $n$ vertices always has exactly $n - 1$ edges.

Adjacency matrix

ACSL often gives graphs as adjacency matrices. For a graph with vertices A, B, C, D:

    A  B  C  D
A [ 0  1  1  0 ]
B [ 1  0  1  1 ]
C [ 1  1  0  0 ]
D [ 0  1  0  0 ]

Entry (i,j) = 1 means there’s an edge from vertex i to vertex j. For undirected graphs, the matrix is symmetric.

Reading degrees from the matrix: The degree of a vertex is the sum of its row (or column, for undirected).

$de g (A) = 0 + 1 + 1 + 0 = 2$
$de g (B) = 1 + 0 + 1 + 1 = 3$
$de g (C) = 1 + 1 + 0 + 0 = 2$
$de g (D) = 0 + 1 + 0 + 0 = 1$

The handshake theorem: The sum of all degrees equals twice the number of edges. This is a fast way to verify your edge count.

$\sum de g (v) = 2∣ E ∣$

In this graph: $2 + 3 + 2 + 1 = 8$ , so there are 4 edges.

Adjacency list

Another common representation. Each vertex lists its neighbors:

A: B, C
B: A, C, D
C: A, B
D: B

This contains the same information as the matrix above.

Counting paths with matrix powers

This is a powerful technique ACSL frequently tests. If $M$ is the adjacency matrix, then $M^{2}$ (the matrix squared) tells you the number of paths of length 2 between each pair of vertices. In general, $M^{p} [i, j]$ gives the number of paths of length $p$ from vertex $i$ to vertex $j$ .

Example: Using the adjacency matrix from above, find the number of paths of length 2 from A to D.

$M^{2} = M \times M$

To compute entry $(A, D)$ of $M^{2}$ , take the dot product of row A and column D:

$M^{2} [A, D] = (0 \times 0) + (1 \times 1) + (1 \times 0) + (0 \times 0) = 1$

There is exactly 1 path of length 2 from A to D, which is A-B-D.

When ACSL asks “how many paths of length 3 exist from X to Y,” compute $M^{3}$ and read the answer from the appropriate cell. For small matrices you can multiply by hand - just be careful with the arithmetic.

Shortest path (Dijkstra’s by hand)

For weighted graphs, ACSL asks for the shortest path between two vertices. On small graphs (5-8 nodes), use this systematic approach:

Set distance to start = 0, all others = infinity
Mark start as “visited”
Update distances to all unvisited neighbors of the current vertex
Pick the unvisited vertex with the smallest distance, mark it visited
Repeat from step 3 until you reach the destination

Example: Find shortest path from A to E.

A --3-- B --2-- E
|       |
4       1
|       |
C --5-- D

Step	Visited	Distances: A B C D E
Start	A	$0$ $3$ $4$ $\infty$ $\infty$
Pick B (3)	A,B	$0$ $3$ $4$ $4$ $5$
Pick C (4)	A,B,C	$0$ $3$ $4$ $4$ $5$
Pick D (4)	A,B,C,D	$0$ $3$ $4$ $4$ $5$
Pick E (5)	All	$0$ $3$ $4$ $4$ $5$

Shortest path from A to E $= 5$ (via A, B, E)

Speed tip: On ACSL-sized graphs, you can often eyeball the 2-3 candidate paths and just add up their weights instead of running the full algorithm.

Minimum spanning tree

A spanning tree connects all vertices with the minimum total edge weight. ACSL uses Kruskal’s algorithm:

Sort all edges by weight (smallest first)
Add each edge if it doesn’t create a cycle
Stop when you have $n - 1$ edges ( $n$ = number of vertices)

Example: Vertices A, B, C, D, E with edges:

B-D: 1
A-B: 3
B-C: 3
C-E: 4
A-C: 5
D-E: 6
B-E: 7

Edge	Weight	Add?	Reason
B-D	$1$	Yes	No cycle
A-B	$3$	Yes	No cycle
B-C	$3$	Yes	No cycle
C-E	$4$	Yes	No cycle
A-C	$5$	No	Would create cycle A-B-C-A

4 edges for 5 vertices. Done.

MST weight $= 1 + 3 + 3 + 4 = 11$

Cycle detection shortcut: An edge creates a cycle if both endpoints are already connected (in the same component). As you add edges, mentally track which vertices are connected.

Counting cycles

ACSL may ask you to count distinct cycles in a directed graph. A cycle starts and ends at the same vertex, visiting no vertex more than once (except the start/end).

Strategy: For small graphs, systematically try each vertex as a starting point and trace all possible paths back to it. Keep track to avoid counting the same cycle twice - list each cycle starting from its smallest-labeled vertex.

Example: In a directed graph with edges $A \to B$ , $B \to C$ , $C \to A$ , $B \to D$ , $D \to A$ :

Cycle 1: A, B, C, A
Cycle 2: A, B, D, A
Total: 2 cycles

Euler and Hamilton paths/circuits

Euler path: visits every edge exactly once. Euler circuit: an Euler path that starts and ends at the same vertex.

The rule:

Euler circuit exists if and only if every vertex has even degree (i.e., $de g (v)$ is even for all $v$ )
Euler path (not circuit) exists if and only if exactly two vertices have odd degree (those are the start and end)

Hamilton path: visits every vertex exactly once. Hamilton circuit: a Hamilton path that returns to the start.

There’s no quick rule for Hamilton paths - you have to try to find one. On small graphs, systematic trial works.

Memory trick: Euler = Edges. Hamilton = … well, it’s the other one (vertices).

Graph coloring (chromatic number)

The chromatic number is the minimum number of colors needed so no two adjacent vertices share a color.

Strategy:

Find the vertex with the highest degree - it needs the most separation from neighbors
Color it, then color its neighbors with different colors
Reuse colors whenever possible for non-adjacent vertices

Example:

A - B
|   |
C - D

A and D are not adjacent, so they can share a color. B and C are not adjacent, so they can share a color. Chromatic number = 2.

Quick check: If the graph contains a triangle (3 vertices all connected to each other), the chromatic number is at least 3. If it contains a complete subgraph of 4 vertices, at least 4.

Trees and forests

A tree is a connected graph with no cycles
A forest is a graph with no cycles (may be disconnected - it’s a collection of trees)
A tree with $n$ vertices has exactly $n - 1$ edges
Any tree with $2 +$ vertices has at least 2 leaves (vertices with degree 1)

Counting trees: If a graph has $n$ vertices, $n - 1$ edges, and is connected, it’s a tree. If it has $n$ vertices and fewer than $n - 1$ edges, it’s disconnected.

Common mistakes

Directed vs undirected confusion. In a directed graph, an edge from A to B does NOT imply one from B to A. Check whether arrows are shown.
Missing edges when reading the problem. Carefully transfer all edges from the problem to your scratch work. One missed edge changes everything.
Kruskal’s: forgetting to check for cycles. Just because an edge is small doesn’t mean you should add it. Always verify no cycle forms.
Euler path: miscounting odd-degree vertices. Count carefully. Two odd-degree vertices means a path exists but not a circuit.
Off-by-one in MST. A spanning tree of n vertices has n-1 edges. Stop there.

Contest strategy

Draw the graph. Always. Even if the problem gives an adjacency matrix.
Label vertices and edge weights clearly
For shortest path: on small graphs, enumerate the 2-3 obvious routes and compare
For MST: sort edges by weight first, then add greedily
For Euler: count degrees first, don’t try to trace the path unless asked
Typical time: 60-90 seconds for degree/path questions, 90-120 for MST/Euler