Formula sheet
Everything countable from Lectures 1–3 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. |
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. |