Mock 9 – Graph Theory (Part 2)

Edges: Cₙ = n, Wₙ = 2n, Kₙ = n(n−1)/2, Kₙ,ₙ = n², Qₙ = n·2ⁿ⁻¹. For the larger n the question intends, these increase in the order C, W, K, Kₙ,ₙ, Q.

A planar graph can be drawn without edge crossings. Graph A is already drawn without crossings. The official key also takes B as planar (it can be redrawn without crossings) and C as non-planar; check by redrawing or by finding a K₅ or K₃,₃ subdivision.

Dirac's theorem: a simple graph with n ≥ 3 vertices in which every vertex has degree at least n/2 is Hamiltonian.

K₃ has 3 spanning trees (n^(n−2)), K₂,₂ (a 4-cycle) has 4, C₅ has 5, and K₄ has 16. Increasing order: A, C, D, B.

A tree on 6 vertices is connected with exactly 5 edges and no cycle. Graphs (A) and (B) each have 5 edges and connect all six vertices. (C) contains a cycle, and (D) has only 4 edges so it is disconnected.

The graph is K₄ with one edge missing (5 edges on 4 vertices). K₄ has 16 spanning trees and each edge lies in 16 × 3/6 = 8 of them, so removing one edge leaves 16 − 8 = 8.

Planar graphs are 4-colourable; bipartite graphs are 2-colourable; PERT uses a probabilistic time model; CPM uses a deterministic one.

In Wₙ (a hub plus an n-cycle), rim vertices have degree 3 and the hub has degree n. It is regular only when n = 3; the official key uses the convention that W₄ has 4 vertices (hub + triangle = K₄), which is 3-regular.

Graph A can be drawn without crossings (its edges can be rerouted around the outside). Graphs B and C contain K₅ or K₃,₃ subdivisions, so they are not planar.

The sum of degrees is twice the number of edges, so it is even (II), and therefore the number of odd-degree vertices must be even (I).

Trees and bipartite graphs are 2-colourable (A, C true), and greedy colouring uses at most d + 1 colours (D true). Bipartite graphs have no odd cycles — even cycles are allowed — so B is wrong. A graph with O(|V|) edges can still contain a large clique, so E is wrong.

There are 6n vertices and 6n − 1 edges. Sum of degrees = 2n + 6n + 3n = 11n = 2(6n − 1), so n = 2: 12 vertices and 11 edges.

A clique is a set of vertices in which every pair is joined by an edge.

Edges = 6 × 4 / 2 = 12. Regions r = e − v + 2 = 12 − 6 + 2 = 8.

A Hamilton circuit alternates sides, so both sides must have the same size; K_{n,n} with n ≥ 2 has one.

45 = 3² × 5, so φ(45) = 45 × (2/3) × (4/5) = 24.

(ii) is Ore's theorem. Dirac's condition needs deg(v) ≥ n/2, not n/3, and the edge-count theorem needs ½(n − 1)(n − 2) + 2 edges, not ⅓. Only (ii) is sufficient.