Formula sheet
Everything countable from Lectures 1–3 and 5–9 on one page. The right-hand column is the mistake that particular line invites.
Counting
Lectures 1–3
| Order and size | n = |V(G)|, m = |E(G)| | Order counts vertices, size counts edges. |
| First Theorem of Graph Theory | Σ deg v = 2m | Halve the degree sum to get m. |
| Corollary 1 | the number of odd vertices is even | Kills any sequence with an odd count of odd degrees. |
| Degree bound (simple graph) | δ(G) ≤ deg v ≤ Δ(G) ≤ n − 1 | Degree n or more is impossible on n vertices. |
| Size of Kₙ | n(n − 1) / 2 | |
| Size of Pₙ, Cₙ | n − 1, n (Cₙ needs n ≥ 3) | Cₙ has one more edge than Pₙ. |
| Complete bipartite K_{s,t} | order s + t, size st | Order adds, size multiplies. |
| Complement | |E(G)| + |E(Ḡ)| = n(n − 1)/2 | |
| Minimum degree forces edges | m ≥ ⌈n·δ(G) / 2⌉ | Round up — m is an integer. |
| Maximum degree caps edges | m ≤ ⌊n·Δ(G) / 2⌋ | |
| k-regular graph on n vertices | exists iff kn is even and k ≤ n − 1 | Noncomplete needs k ≤ n − 2. |
| Densest bipartite graph of order n | ⌊n² / 4⌋ edges (K⌊n/2⌋,⌈n/2⌉) | |
| Order n with exactly k components | n − k ≤ m ≤ C(n − k + 1, 2) | Max is one big clique plus k − 1 isolated vertices. |
Binary operations
Lecture 2 — G has (n₁, m₁), H has (n₂, m₂)
| Union G ∪ H | |V| = n₁ + n₂, |E| = m₁ + m₂ | Always disconnected. |
| Join G + H | |V| = n₁ + n₂, |E| = m₁ + m₂ + n₁n₂ | Adds every crossing edge. |
| Cartesian product G × H | |V| = n₁n₂, |E| = n₁m₂ + n₂m₁ | Cross-multiplied. Not m₁m₂, not n₁m₁ + n₂m₂. |
| Degree in G × H | deg(u, v) = deg_G(u) + deg_H(v) | |
| Adjacency in G × H | (u,v) ~ (x,y) iff (u = x ∧ vy ∈ E(H)) or (v = y ∧ ux ∈ E(G)) | Exactly one coordinate moves. |
| Drawing G × H | n₁ copies of H, joined at corresponding vertices along edges of G | Corresponding vertices only — that is what separates it from the join. |
Hierarchies you must not collapse
Lecture 1
| Walk ⊋ trail ⊋ path | walk: anything repeats · trail: no repeated edge · path: no repeated vertex | Every path is a trail; no converse. |
| Circuit ⊋ cycle | circuit: closed trail, length ≥ 3 · cycle: circuit with no repeated vertex except first = last | Every cycle is a circuit; no converse. |
| Subgraph ⊋ induced subgraph | subgraph: V, E both contained · induced: must carry EVERY edge of G between the chosen vertices | G[S] is where marks quietly vanish. |
| Spanning subgraph | same vertex set as G | G − e is spanning; G − v is not. |
| Length of a walk | number of edges traversed, counting repeats | A sequence of k + 1 vertices has length k. |
| Adjacent vs incident | adjacent: vertex–vertex or edge–edge · incident: vertex–edge |
Theorems
Lectures 1–3
| Theorem 1 (Lec 1) | G is connected ⟺ G has a u–v walk for every pair u, v | A walk suffices, because every u–v walk contains a u–v path. |
| Bipartite characterisation (Lec 2) | a nontrivial G is bipartite ⟺ G has no odd cycles | Triangle-free is not enough — C₅. |
| Complement (Lec 2) | G disconnected ⟹ Ḡ connected | One-way only. P₄ and its complement are both connected. |
| First Theorem (Lec 3) | Σ deg v = 2m | Each edge is counted once at each endpoint. |
| Corollary 1 (Lec 3) | every graph has an even number of odd vertices | |
| Digraph degrees (Lec 3) | Σ od(v) = Σ id(v) = m | m, not 2m — an arc has one tail and one head. |
| Pseudograph degree (Lec 3) | each loop at v contributes 2 to deg v | This is exactly what keeps Σ deg v = 2m true. |
Isomorphism
Lecture 5
| Equal vs isomorphic | G = H: V(G) = V(H) and E(G) = E(H) · G ≅ H: relabelling makes them equal | Isomorphic graphs need not be equal. |
| Isomorphism | a bijection f : V(G) → V(H) with uv ∈ E(G) ⟺ f(u)f(v) ∈ E(H) | ⟺, not ⟹: non-adjacency must be preserved too. |
| Theorem 2.1.2 | G ≅ H ⟹ same order and same size | |
| Theorem 2.1.3 | deg f(v) = deg v | Map each vertex only to one of the same degree. |
| Corollary 2.1.4 | G ≅ H ⟹ same degree sequence | The converse fails: same sequence proves nothing. |
| Corollary 2.1.5 | f(e) has the same end-degrees as e | Same degree sequence, but an edge joining two 3s in G and none in H ⟹ G ≇ H. |
| Proving G ≇ H | one differing invariant: n, m, degree sequence, end-degrees of edges, connectedness, a cycle length | |
| Proving G ≅ H | write down the bijection and check every edge | Agreeing invariants are never a proof. |
| Self-complementary (G ≅ Ḡ) | needs m = n(n − 1)/4, so n ≡ 0 or 1 (mod 4) | P₄ and C₅ work; no graph of order 6 or 7 does. |
| Graphs of order 4, up to isomorphism | 11 (by size 0–6: 1, 1, 2, 3, 2, 1, 1) |
Trees and bridges
Lecture 6
| Bridge | G − e disconnected ⟺ k(G − e) = k(G) + 1 | Deleting one edge adds at most one component. |
| Theorem 6.1 | e is a bridge ⟺ e lies on no cycle | A bridge need not touch a leaf. |
| Tree · forest | tree: acyclic and connected · forest: acyclic | Each component of a forest is a tree. |
| Theorem 6.2 | G is a tree ⟺ every two vertices are joined by a unique path | |
| Theorem 6.3 | every nontrivial tree has ≥ 2 end-vertices | At least two — exactly two only for paths. |
| Theorem 6.4 | tree of order n has size n − 1, so Σ deg v = 2(n − 1) | Use this sum for every “how many leaves” count. |
| Corollary 6.6 | forest of order n with k components has size n − k | |
| Theorem 6.7 | connected of order n ⟹ m ≥ n − 1 | |
| Theorem 6.8 | any two of: connected, acyclic, m = n − 1 ⟹ tree | One condition alone proves nothing. |
| Double star · caterpillar | double star: exactly two non-leaves (adjacent) · caterpillar: order ≥ 3, deleting the leaves leaves a path (the spine) | Paths, stars and double stars are all caterpillars. |
| Counting leaves | x leaves + known degrees: Σ deg = 2(n − 1), solve with the vertex count | Set up two equations: one for vertices, one for degrees. |
Spanning trees
Lecture 7 — G connected and weighted
| Spanning tree | spanning subgraph that is a tree: n vertices, n − 1 edges | Delete m − n + 1 edges to get one. |
| Theorem 7.1 | every connected graph has a spanning tree | A disconnected graph has none. |
| Weight of a subgraph | w(H) = Σ w(e) over e ∈ E(H) | |
| Minimum spanning tree | spanning tree of least weight among all spanning trees | All spanning trees have n − 1 edges; only the weight differs. |
| Kruskal, steps 1–2 | cheapest edge, then the next cheapest | Two edges can never form a cycle — no check needed yet. |
| Kruskal, step 3 on | cheapest remaining edge that forms no cycle with those chosen | Picks may lie in different parts of G until the end. |
| Prim, step 1 | any vertex u; cheapest edge at u | Not the cheapest edge of all of G — that is Kruskal. |
| Prim, later steps | cheapest edge with exactly one end on the tree so far | Exactly one: both ends in the tree closes a cycle. |
| When to stop | after n − 1 edges | |
| Ties | either edge may be taken; the weight of the result is the same | Different trees, same minimum weight. |
| Theorems 7.2, 7.3 | Kruskal and Prim both produce a minimum spanning tree | Both are greedy: no choice is ever undone. |
Cut-vertices and blocks
Lecture 8
| G − v, G − U | delete the vertices and every edge incident with them | Not spanning: the vertices go too. |
| Cut-vertex | G − v disconnected (in a component, for disconnected G) | A leaf is never a cut-vertex. |
| Bridge ⟹ cut-vertex | connected, order ≥ 3, has a bridge ⟹ has a cut-vertex (Cor 5.2) | K₂ is the exception. The converse fails — two triangles sharing a vertex. |
| Theorem 5.1 | v on a bridge is a cut-vertex ⟺ deg v ≥ 2 | |
| Corollary 5.4 | v is a cut-vertex ⟺ some u, w ≠ v have v on EVERY u – w path | Every path, not some path. |
| Nonseparable | nontrivial, connected, no cut-vertices | K₂ counts; K₁ does not. |
| Theorem 5.7 | order ≥ 3: nonseparable ⟺ every two vertices lie on a common cycle | Every two adjacent vertices is not enough. |
| Block | maximal nonseparable subgraph | Each bridge, with its ends, is a block. |
| Two distinct blocks | edge-disjoint; share ≤ 1 vertex; a shared vertex is a cut-vertex |
Connectivity
Lecture 9
| Vertex-cut | U with G − U disconnected; exists ⟺ G not complete (G connected) | |
| κ(G) | min |U| with G − U disconnected or trivial; 0 ≤ κ(G) ≤ n − 1 | “Or trivial” is what gives Kₙ a value. |
| κ values | κ = 0 ⟺ disconnected · κ = 1 ⟺ K₂ or has a cut-vertex · κ ≥ 2 ⟺ nonseparable, n ≥ 3 | |
| Edge-cut | X with G − X disconnected | Minimum ⟹ minimal, but not conversely. |
| λ(G) | size of a minimum edge-cut; λ = 0 ⟺ disconnected or trivial · λ = 1 ⟺ connected with a bridge | |
| Theorem 5.11 (Whitney) | κ(G) ≤ λ(G) ≤ δ(G) | Vertices first, then edges, then degree. |
| Kₙ (Thm 5.10) | κ = λ = n − 1 | |
| K_{s,t} | κ = min(s, t) | Delete the smaller partite set. |
| Cₙ, Pₙ | κ(Cₙ) = λ(Cₙ) = 2 · κ(Pₙ) = λ(Pₙ) = 1 (n ≥ 3) |
Does it exist? — a decision procedure
Lecture 3, Exercise 1 — run these in order
| 1. Parity | is Σ (required degrees) even? | If odd, stop: no such graph, by the First Theorem. |
| 2. Degree ceiling | is every required degree ≤ n − 1? | If not, stop: no vertex can be adjacent to itself. |
| 3. Edge window | ⌈nδ/2⌉ ≤ m ≤ ⌊nΔ/2⌋ | Also check any class-specific ceiling, e.g. ⌊n²/4⌋ for bipartite. |
| 4. Structure | greedily satisfy the largest degree first, then reduce and repeat | 1, 3, 3, 3 on four vertices passes steps 1–3 and still fails here. |
| 5. Otherwise | construct one and draw it | Any valid example scores; you are never asked for a unique answer. |