L37 Solutions — Introduction to Networks

1. Basic graph terminology. Fluency

   • (a) 5 vertices, 6 edges.
   • (b) deg(A)=3 (AB,AC,AD), deg(B)=2 (AB,BC), deg(C)=3 (AC,BC,CE), deg(D)=2 (AD,DE), deg(E)=2 (CE,DE).
   • (c) Sum = 3+2+3+2+2 = 12 = 2×6. ✓
   • (d) Odd-degree vertices: A (3), C (3). 2 odd-degree vertices.

2. Handshaking lemma. Fluency

   • (a) Sum of degrees = 2 × 5 = 10.
   • (b) Sum = 2+3+4+5+2 = 16. Edges = 16/2 = 8.
   • (c) No. The handshaking lemma states the sum of all degrees equals 2×(edges), so the sum must be even. Three odd numbers sum to an odd number — impossible.
   • (d) Sum = 4×3 = 12. Edges = 12/2 = 6. (This is K₄.)

3. Complete graphs and trees. Fluency

   • (a) K₆: 6(6−1)/2 = 15 edges.
   • (b) A tree with 8 vertices has 7 edges (n−1).
   • (c) n(n−1)/2 = 21 ⇒ n(n−1) = 42 ⇒ n = 7 (since 7×6=42).
   • (d) True — a tree is defined as a connected acyclic graph, so by definition a path exists between every pair of vertices.

4. Graph properties. Fluency

   • (a) A directed graph has arrows on edges (e.g. one-way streets). An undirected graph has edges with no direction (e.g. railway lines you can travel both ways).
   • (b) Sum = 4+4+4+4 = 16. Edges = 8. All 4 vertices have degree 3 in K₄... wait: K₄ has 4 vertices each with degree 3. But here degree = 4, so this is K₅ with all 5 vertices having degree 4. Edges = 5×4/2 = 10.
   • (c) Yes. Example: a path graph P₄ (A–B–C–D) and a star graph (B connected to A, C, D with centre B) both have degree sequence (1,1,1,3) but different structures.
   • (d) Paths from A to D: A–B–C–D (5+8+2=15), A–C–D (3+2=5), A–C–B–D (3+8+9=20). Shortest: A–C–D = 5.

5. Reading a weighted network. Understanding

   • (a) 5 vertices (P,Q,R,S,T), 6 edges.
   • (b) deg(P)=2, deg(Q)=3, deg(R)=3, deg(S)=3, deg(T)=1. Sum=2+3+3+3+1=12=2×6. ✓
   • (c) 8+6+5+10+7+4 = 40 km.
   • (d) Paths from P to T: P–Q–S–T (8+10+4=22), P–R–S–T (6+7+4=17), P–Q–R–S–T (8+5+7+4=24). Shortest: P–R–S–T = 17 km.

6. Adjacency and connectivity. Understanding

   • (a) P: {Q, R}. Q: {P, R, S}. R: {P, Q, S}. S: {Q, R, T}. T: {S}.
   • (b) Yes — a path exists between every pair of vertices (e.g. P to T via P–R–S–T).
   • (c) 1 edge — one edge connecting the isolated vertex to any other vertex makes it reachable.
   • (d) A connected graph on 5 vertices needs at least 4 edges (a tree with n−1 edges).

7. Real-world graph modelling. Understanding

   • (a) Every person follows every other: K₅. Edges = 5×4/2 = 10.
   • (b) Any arrangement where all 4 vertices have degree ≥ 2. Example: a cycle graph C₄ (A–B–C–D–A) gives each office exactly 2 connections.
   • (c) deg(Syd)=2, deg(Mel)=2, deg(Bne)=2, deg(Ade)=2. All degree 2 — no city has higher degree; they’re equal.
   • (d) Yes, connected. Ade–Mel–Syd is a valid path from Adelaide to Sydney.

8. Graph types. Understanding

   • (a) Each of {1,2,3} connects to both {a,b}: edges 1a, 1b, 2a, 2b, 3a, 3b.
   • (b) 6 edges (3×2).
   • (c) In K₃, all three vertices are mutually connected, forming a triangle. A bipartite graph cannot contain an odd cycle. A triangle is a 3-cycle (odd), so K₃ is not bipartite.
   • (d) A loop counts as 2 towards the degree. So minimum degree of V = 2.

9. Degree sequences and graph construction. Problem Solving

   • (a) Sum = 3+3+2+2+2 = 12 = 2×6. Even sum → valid. Example: vertices A,B,C,D,E; A–B,A–C,A–D,B–C,B–E,C–D (verify degrees).
   • (b) Sum = 4+3+3+2+2 = 14 = 2×7. Even sum → potentially valid. A simple graph on 5 vertices can have max degree 4. This sequence is achievable.
   • (c) Sum = 3+3+3+1 = 10 = 2×5. Valid sum. Can we build it? 4 vertices, one has degree 1. The degree-1 vertex connects to one of the degree-3 vertices. The 3 degree-3 vertices form K₃ plus one extra edge. Valid: triangle A–B–C–A plus edge A–D gives deg(A)=3,deg(B)=2... not matching. Requires more careful construction — the sequence is valid by Erdős–Gallai theorem.
   • (d) All vertices have degree n−1, meaning each connects to every other vertex. This is the complete graph K_n. Edges = n(n−1)/2.

10. Network design. Problem Solving

    • (a) 8 edges as listed; draw with 6 vertices and weighted connections.
    • (b) 6 suburbs need at least 5 edges (a spanning tree has n−1 = 5 edges).
    • (c) 12+8+5+9+11+7+6+10 = $68 000.
    • (d) Choose 5 cheapest edges that keep all connected: BC=5, CF=? (no CF edge) — use B–C(5), A–C(8), D–F(6), C–E(7), B–D(9). Total = 5+8+6+7+9 = $35 000 exactly. All 6 suburbs connected.