Graph Theory / Cram

Cram

Every lecture in five minutes. Each section says what the idea is in plain words, then gives the exact definitions and theorems, with the trap that loses marks under each.

8 lectures · 99 definitions and theorems

Lecture 1

Basic concepts

A graph is dots (vertices) and lines (edges). This lecture names the parts, the pieces you can cut out of a graph, the ways to move through it, and what it means to be in one piece.

Practise it:Edge-Set Builder Walks, Trails & Paths Subgraph Surgery

1.1Graphs and their parts

n counts vertices, m counts edges. Two vertices joined by an edge are adjacent; a vertex and an edge touching it are incident.

Graph G = (V, E): A finite nonempty set V of vertices together with a set E of 2-element subsets of V called edges.Trap: 2-element subsets ⇒ no loops and no multiple edges in a simple graph.
Order and size: Order = |V(G)| = n, the number of vertices. Size = |E(G)| = m, the number of edges.Trap: Order counts vertices, size counts edges — never the other way round.
Equal graphs: G = H means V(G) = V(H) and E(G) = E(H).Trap: Same picture or same counts is not equality.
Trivial graph: A graph with exactly one vertex. It is connected.
Adjacent: If uv ∈ E(G), then u and v are adjacent. Distinct edges sharing a vertex are adjacent edges.
Incident: If e = uv, then u and e are incident with each other, as are v and e.Trap: Incidence is vertex-to-edge; adjacency is vertex-to-vertex or edge-to-edge.
Neighbours: If uv ∈ E(G), then u and v are neighbours of each other.

1.2Subgraphs

A subgraph keeps some vertices and some edges. Spanning keeps every vertex. Induced keeps every edge between the vertices it keeps.

Subgraph H ⊆ G: V(H) ⊆ V(G) and E(H) ⊆ E(G).
Proper subgraph: H ⊆ G with V(H) a proper subset of V(G) OR E(H) a proper subset of E(G).Trap: It is an OR, not an AND.
Spanning subgraph: A subgraph with the same vertex set as G.
Induced subgraph: A subgraph F such that whenever u, v ∈ V(F) and uv ∈ E(G), then uv ∈ E(F). For S ⊆ V(G), the subgraph induced by S is written G[S] or ⟨S⟩_G.Trap: You must carry over EVERY edge of G between the chosen vertices.
G − e and G − X: G − e is the spanning subgraph with edge set E(G) − {e}. For a set X of edges, E(G − X) = E(G) − X.Trap: Deleting edges never deletes vertices.
G − v and G − U: G − v has all vertices except v and all edges except those incident with v. G − U has vertex set V(G) − U and all edges of G joining two vertices of V(G) − U.

1.3Walks, trails, paths, circuits, cycles

A walk may repeat anything, a trail repeats no edge, a path repeats no vertex. Closed versions: circuit (closed trail), cycle (closed path).

Walk: A u–v walk is a sequence of vertices from u to v in which consecutive vertices are adjacent. Vertices and edges may repeat. Its length is the number of edges traversed, counting repeats.
Open / closed / trivial walk: Closed if u = v, open if u ≠ v. A walk of length 0 is a trivial walk.
Trail: A u–v walk in which no edge is traversed more than once.Trap: Vertices MAY repeat in a trail.
Path: A u–v walk in which no vertex is repeated.Trap: path ⇒ trail ⇒ walk, and none of the converses hold.
Circuit: A closed trail of length 3 or more: it begins and ends at the same vertex and repeats no edge.
Cycle: A circuit that repeats no vertex except the first = last. A k-cycle has length k; a 3-cycle is a triangle. Odd cycle = odd length.Trap: Every cycle is a circuit; not every circuit is a cycle.
Deleting a vertex from a cycle: Gives a path.

1.4Connectedness

Connected means you can get from any vertex to any other. A component is one connected piece that cannot grow; k(G) counts them.

u and v are connected: G contains some u–v path.
Connected graph: Every two vertices of G are connected. The trivial graph is connected.
Component: A connected subgraph of G that is not a proper subgraph of any other connected subgraph of G — that is, a maximal connected subgraph. The number of components is k(G), and G is connected iff k(G) = 1.
Theorem 1: G is connected if and only if G contains a u–v walk for every pair u, v of vertices.Trap: The point is that a WALK suffices — every u–v walk contains a u–v path.

Lecture 2

Classes and operations

The named families of graphs (paths, cycles, complete, bipartite), how far apart vertices are, and the ways to build a new graph from two old ones.

Practise it:Classes & Operations Graph Inspector

2.1Distance and diameter

Distance is the length of the shortest path between two vertices. Diameter is the largest distance in the graph.

Distance d(u,v): The smallest length of any u–v path in G. A u–v path of that length is a u–v geodesic.
Diameter: diam(G) is the greatest distance between any two vertices of a connected graph G.

2.2Common classes

Pₙ is a line, Cₙ a ring, Kₙ has every edge, the complement Ḡ has exactly the edges G is missing.

Pₙ and Cₙ: Pₙ: vertices relabelled v₁,…,vₙ with edges v₁v₂,…,vₙ₋₁vₙ — n − 1 edges. Cₙ (n ≥ 3): the same plus v₁vₙ — n edges.
Complete graph Kₙ: Every two distinct vertices are adjacent. Size = n(n − 1)/2, the maximum possible on n vertices.
Complement Ḡ: Same vertex set as G; uv ∈ E(Ḡ) iff uv ∉ E(G) (u ≠ v). Hence |E(G)| + |E(Ḡ)| = n(n−1)/2.
Empty graph: K̄ₙ: n vertices and no edges.
Complement theorem: If G is disconnected, then Ḡ is connected.Trap: One-way only — the converse is false (e.g. P₄).

2.3Bipartite graphs

Split the vertices into two sides with every edge crossing between them. Possible exactly when there is no odd cycle.

Bipartite graph: V(G) partitions into partite sets U and W such that every edge joins a vertex of U to a vertex of W.
Bipartite characterisation: A nontrivial graph G is bipartite if and only if G contains no odd cycles.Trap: Triangle-free is not enough: C₅ is triangle-free but not bipartite.
Complete bipartite K_{s,t}: Every vertex of U is adjacent to every vertex of W. Order s + t, size st. If s = 1 or t = 1 it is a star.

2.4Union, join, Cartesian product

Union puts two graphs side by side. Join also adds every edge between them. The product puts a copy of H at every vertex of G.

Union G ∪ H: For vertex-disjoint G and H: vertex set V(G) ∪ V(H), edge set E(G) ∪ E(H). The result is disconnected.
Join G + H: G ∪ H together with all edges joining a vertex of G to a vertex of H. |V| = n₁ + n₂, |E| = m₁ + m₂ + n₁n₂.
Cartesian product G × H: V = V(G) × V(H). Distinct (u,v) and (x,y) are adjacent iff (u = x and vy ∈ E(H)) or (v = y and ux ∈ E(G)). |V| = n₁n₂, |E| = n₁m₂ + n₂m₁.Trap: Cross-multiplied: n₁m₂ + n₂m₁, not m₁m₂.
Drawing G × H informally: Replace each vertex x of G by a copy Hₓ of H; if u and v are adjacent in G, join corresponding vertices of H_u and H_v.
Degree in G × H: deg(u,v) = deg_G(u) + deg_H(v).

2.5Digraphs

Edges get a direction: an arc (u, v) points from u to v.

Digraph: A finite nonempty vertex set V with a set E of ordered pairs of distinct vertices, called directed edges or arcs.
Adjacent to / adjacent from: If (u,v) is an arc, then u is adjacent TO v, and v is adjacent FROM u.
Oriented graph: A digraph in which, for each pair u, v, at most one of (u,v) and (v,u) is an arc. Equivalently, an orientation of some graph G.

Lecture 3

Degrees

The degree of a vertex is how many edges touch it. Adding up all the degrees counts every edge twice, and most counting and existence questions come down to that one fact.

Practise it:Degree & Handshake Construction Challenges

3.1Degree and its bounds

deg v is the number of edges at v. δ is the smallest degree, Δ the largest, and no vertex of a simple graph exceeds n − 1.

Degree: deg v = the number of edges incident with v. In a simple graph deg v = |N(v)|, where N(v) is the neighbourhood of v.
Isolated vertex / end-vertex: Isolated vertex: degree 0. End-vertex (leaf): degree 1.
δ(G) and Δ(G): Minimum and maximum degree over all vertices. For any vertex v of a simple graph of order n: δ(G) ≤ deg v ≤ Δ(G) ≤ n − 1.
Even / odd vertex: A vertex of even degree is even; of odd degree, odd.
Degree bound in a simple graph: Δ(G) ≤ n − 1. A vertex can be adjacent to at most every other vertex.

3.2The First Theorem

Σ deg v = 2m, so the number of odd-degree vertices is always even. Use it to rule out degree sequences.

First Theorem of Graph Theory: If G has size m, then Σ_{v ∈ V(G)} deg v = 2m. Proof: summing degrees counts each edge twice, once at each endpoint.
Corollary 1: Every graph has an even number of odd vertices.Trap: This kills any degree sequence with an odd number of odd entries.
k-regular graph: Every vertex has degree k. Exists on n vertices iff kn is even and k ≤ n − 1; it is noncomplete iff additionally k ≤ n − 2.

3.3Loops and arcs

A loop adds 2 to its vertex's degree. In a digraph, out-degrees and in-degrees each sum to m.

Degree in a pseudograph: The number of edges incident with v, where each loop at v contributes 2.
Indegree and outdegree: For v in a digraph D: od(v) = number of vertices to which v is adjacent; id(v) = number of vertices from which v is adjacent. Σ od(v) = Σ id(v) = m.Trap: For arcs the total is m, not 2m.

Lecture 5

Isomorphism

Two graphs are isomorphic when they are the same graph with different labels. Prove it with a bijection that keeps every edge an edge; disprove it with one property they disagree on.

Practise it:Isomorphism

5.1What an isomorphism is

A one-to-one matching of vertices where u, v adjacent ⇔ f(u), f(v) adjacent.

Equal vs isomorphic graphs: G = H when V(G) = V(H) and E(G) = E(H). G ≅ H when the vertices of G and H can be labelled (or relabelled) to produce two equal graphs — they have the same structure.Trap: Isomorphic graphs need not be equal; equal graphs are always isomorphic.
Preserves adjacency / non-adjacency: A vertex function f : V(G) → V(H) preserves adjacency if f(u) and f(v) are adjacent whenever u and v are; it preserves non-adjacency if f(u) and f(v) are non-adjacent whenever u and v are.
Structure-preserving bijection: A vertex bijection f : V(G) → V(H) that preserves adjacency and non-adjacency: u and v are adjacent in G ⇔ f(u) and f(v) are adjacent in H. Such an f is an isomorphism.Trap: The ⇔ matters: adjacency alone is not enough.

5.2What it preserves

Order, size, every vertex's degree, and so the degree sequence. Matching these is necessary, never enough.

Theorem 2.1.2: If G and H are isomorphic, they have the same number of vertices and the same number of edges — an isomorphism maps both sets bijectively.
Theorem 2.1.3: If f : G → H is an isomorphism and v ∈ V(G), then deg f(v) = deg v.
Corollary 2.1.4: Isomorphic graphs have the same degree sequence.Trap: Not the converse: the same degree sequence does not make two graphs isomorphic.
Corollary 2.1.5: If f : G → H is an isomorphism and e ∈ E(G), the endpoints of f(e) have the same degrees as the endpoints of e.

5.3Proving and disproving

Not isomorphic: name one invariant that differs. Isomorphic: write out the bijection.

Showing G ≇ H: Find one invariant that differs: order, size, degree sequence, the degrees at the ends of some edge, connectedness, a cycle length. Showing G ≅ H needs an explicit bijection that carries E(G) onto E(H).Trap: Agreeing invariants never prove isomorphism.

Lecture 6

Bridges and trees

A bridge is an edge whose removal splits the graph. A tree is connected with no cycles, so every edge is a bridge, and a tree on n vertices always has n − 1 edges.

Practise it:Bridges & Trees

6.1Bridges

An edge is a bridge exactly when it is on no cycle.

Bridge: An edge e of a connected graph G is a bridge if G − e is disconnected. In a disconnected graph, e is a bridge if it is a bridge of some component. Equivalently, k(G − e) = k(G) + 1.Trap: A bridge need not touch an end-vertex.
Theorem 6.1: An edge e of a graph G is a bridge if and only if e lies on no cycle of G.

6.2Trees and kinds of tree

Tree: connected and acyclic. Forest: acyclic, possibly in pieces. Stars, double stars and caterpillars are named shapes.

Tree and forest: A graph is acyclic if it has no cycles. A tree is an acyclic connected graph. An acyclic graph is a forest; each component of a forest is a tree.Trap: Every tree is a forest; a forest is a tree only when connected.
Double star: A tree containing exactly two vertices that are not end-vertices. Those two are necessarily adjacent.
Caterpillar: A tree of order 3 or more whose removal of end-vertices produces a path, called the spine. Every path and star (order ≥ 3) and every double star is a caterpillar.
Rooted tree: A tree T with one vertex r designated as the root. Usually drawn with r at the top and the other vertices below in levels by their distance from r.

6.3Tree theorems

One path between any two vertices, at least two leaves, n − 1 edges. Any two of connected, acyclic, m = n − 1 make a tree.

Theorem 6.2: A graph G is a tree if and only if every two vertices of G are connected by a unique path.Trap: Unique is the point — a second u–v path would close a cycle.
Theorem 6.3: Every nontrivial tree has at least two end-vertices.Trap: At least two, not exactly two — exactly two only for paths.
Theorem 6.4: Every tree of order n has size n − 1. Combine with Σ deg v = 2(n − 1) to solve the “how many end-vertices” problems.
Corollary 6.6: Every forest of order n with k components has size n − k.
Theorem 6.7: The size of every connected graph of order n is at least n − 1.
Theorem 6.8: Let G have order n and size m. If G satisfies any two of (1) connected, (2) acyclic, (3) m = n − 1, then G is a tree.Trap: Any one alone is not enough.

Lecture 7

Minimum spanning trees

A spanning tree reaches every vertex with no cycle. On a weighted graph, Kruskal and Prim each build the cheapest one by always taking the cheapest safe edge.

Practise it:Minimum Spanning Trees

7.1Spanning trees and weight

Every connected graph has a spanning tree. w(T) is the sum of its edge weights; a minimum spanning tree has the smallest w(T).

Spanning tree: A spanning subgraph H of a connected graph G such that H is a tree. It has all n vertices and n − 1 edges.
Theorem 7.1: Every connected graph contains a spanning tree.Trap: Disconnected graphs have none.
Weighted graph and w(H): A connected graph each of whose edges e is assigned a number w(e), its cost or weight. For a subgraph H, w(H) = Σ_{e ∈ E(H)} w(e).
Minimum spanning tree: A spanning tree of G whose weight is minimum among all spanning trees of G. Finding one is the Minimum Spanning Tree Problem — used in designing computer, communication and transportation networks.

7.2Kruskal and Prim

Kruskal: cheapest edge anywhere that makes no cycle. Prim: cheapest edge leaving the tree grown so far. Both are greedy, both are optimal.

Kruskal’s Algorithm: e₁: any edge of minimum weight. e₂: any remaining edge of minimum weight. From e₃ on: any remaining edge of minimum weight that does not produce a cycle with the edges already selected. Continue until a spanning tree is produced.Trap: The selected edges may be disconnected until the end.
Prim’s Algorithm: From an arbitrary vertex u, select an edge of minimum weight incident with u as e₁. For e₂, …, eₙ₋₁, select an edge of minimum weight among those having exactly one of its vertices incident with an edge already selected.Trap: Exactly one end in the tree — that is what prevents cycles.
Theorems 7.2 and 7.3: Kruskal’s Algorithm and Prim’s Algorithm each produce a minimum spanning tree in a connected weighted graph.
Greedy algorithm: An algorithm that makes the best-looking choice at each step without reconsidering previous choices, aiming to end at an optimal solution. Kruskal and Prim are both greedy.

Lecture 8

Cut-vertices and blocks

A cut-vertex is a vertex whose removal splits the graph. A graph with none is nonseparable, and the blocks are the largest nonseparable pieces a graph breaks into.

Practise it:Cut-Vertices & Blocks

8.1Cut-vertices

v is a cut-vertex when G − v has more pieces, so some two vertices can only reach each other through v.

G − v and G − U: G − v: all vertices except v, all edges except those incident with v. G − U (U a proper subset of V(G)): vertex set V(G) − U and every edge of G joining two vertices of V(G) − U. Both are induced subgraphs.
Cut-vertex: A vertex v of a connected graph G with G − v disconnected. In a disconnected graph, v is a cut-vertex if it is a cut-vertex of a component.Trap: An end-vertex is never a cut-vertex.
Bridges and cut-vertices: Except for K₂, every connected graph with bridges contains cut-vertices (Corollary 5.2: order ≥ 3 with a bridge ⟹ a cut-vertex).Trap: The converse is false: two triangles sharing a vertex have a cut-vertex and no bridge.
Theorem 5.1: Let v be a vertex incident with a bridge in a connected graph G. Then v is a cut-vertex of G if and only if deg v ≥ 2.
Theorem 5.3: Let v be a cut-vertex of a connected graph G and u, w vertices in distinct components of G − v. Then v lies on every u – w path in G.
Corollary 5.4: A vertex v of a connected graph G is a cut-vertex if and only if there exist vertices u and w distinct from v such that v lies on every u – w path of G.Trap: Every path, not some path.

8.2Nonseparable graphs and blocks

Nonseparable: connected with no cut-vertex, so every two vertices share a cycle. Blocks share at most a cut-vertex, never an edge.

Nonseparable graph: A nontrivial connected graph with no cut-vertices. K₂ is nonseparable; K₁ is not (it is trivial).
Theorem 5.7: A graph of order at least 3 is nonseparable if and only if every two vertices lie on a common cycle.Trap: Every two vertices — “every two adjacent vertices” is not enough.
Block: A maximal nonseparable subgraph of G: nonseparable and not a proper subgraph of any other nonseparable subgraph. Blocks are to nonseparable what components are to connected.
Properties of blocks: Distinct blocks B₁, B₂ of a nontrivial connected graph (a) are edge-disjoint, (b) have at most one vertex in common, and (c) if they share a vertex v, then v is a cut-vertex of G.

Lecture 9

Connectivity κ and λ

How hard a graph is to split. κ is the fewest vertices, λ the fewest edges, whose removal disconnects it, and both are at most the minimum degree.

Practise it:Connectivity κ and λ

9.1Vertex-connectivity κ

The size of the smallest vertex set whose removal disconnects G or leaves one vertex.

Vertex-cut: A set U of vertices of G such that G − U is disconnected. A vertex-cut of minimum cardinality is a minimum vertex-cut. A connected graph contains a vertex-cut if and only if it is not complete.
Vertex-connectivity κ(G): The minimum |U| over all U ⊆ V(G) such that G − U is disconnected or trivial. For a graph of order n, 0 ≤ κ(G) ≤ n − 1, and κ(Kₙ) = n − 1.Trap: “Or trivial” is what gives complete graphs a value.
κ remarks: A nontrivial G has κ = 0 iff it is disconnected. κ = 1 iff G = K₂ or G is connected with cut-vertices. κ ≥ 2 iff G is nonseparable of order 3 or more.

9.2Edge-connectivity λ

The size of the smallest edge set whose removal disconnects G.

Edge-cut: A set X of edges of a nontrivial graph G such that G − X is disconnected. Minimal: no proper subset of X is an edge-cut. Minimum: an edge-cut of minimum cardinality.Trap: Every minimum edge-cut is minimal; not every minimal edge-cut is minimum.
Edge-connectivity λ(G): The cardinality of a minimum edge-cut of a nontrivial G: the minimum |X| with G − X disconnected or trivial. For order n, 0 ≤ λ(G) ≤ n − 1.
λ remarks: λ(G) = 0 iff G is disconnected or trivial. λ(G) = 1 iff G is connected and contains a bridge.
Theorem 5.10: For every positive integer n, λ(Kₙ) = n − 1.

9.3Putting them together

κ ≤ λ ≤ δ: removing the edges at a minimum-degree vertex always cuts it off.

Theorem 5.11: For every graph G, κ(G) ≤ λ(G) ≤ δ(G), where δ(G) is the minimum degree.Trap: Vertex cuts are never bigger than edge cuts — not the other way round.
Network survivability: The capacity of a network to keep its nodes connected after some edges or nodes are removed. κ and λ quantify it.