Practice Maths

← Graphs and Networks › Graph Theory — Definitions and Representations › Solutions

Solutions — Graph Theory — Definitions and Representations

  1. Fluency Graph with vertices A, B, C, D; edges AB (twice), BC, CD, DA.
    (a) 4 vertices
    (b) 5 edges (AB counted twice)
    (c) deg(A) = 3 (edges: AB, AB, DA), deg(B) = 3 (edges: AB, AB, BC), deg(C) = 2 (edges: BC, CD), deg(D) = 2 (edges: CD, DA)

    Check: 3 + 3 + 2 + 2 = 10 = 2 × 5 ✓ (Handshaking Lemma holds)
  2. Fluency Degrees 1, 2, 3, 4, 4. Verify Handshaking Lemma.
    Sum of degrees = 1 + 2 + 3 + 4 + 4 = 14
    Number of edges = 14 / 2 = 7 edges

    The Handshaking Lemma: Σdeg(v) = 2|E| → 14 = 2 × 7 ✓
  3. Fluency Graph with edges AB, BC, CD, DA, AC. Classify each sequence.
    (a) A → B → C → A: uses edges AB, BC, CA — starts and ends at A, no repeated edges or vertices (except A). Cycle

    (b) A → B → C → D → A: uses edges AB, BC, CD, DA — visits all 4 vertices and returns to start, no repeats. Cycle (Hamiltonian cycle)

    (c) A → C → B → A → D: uses edges AC, CB, BA, AD — vertex A is visited twice (at start and in the middle). This is a trail (no edge is repeated, but vertex A is repeated, so not a path).
  4. Fluency Complete graph K4.
    Number of edges = n(n−1)/2 = 4 × 3 / 2 = 6 edges
    Each vertex is connected to the other 3 vertices, so degree of each vertex = 3

    Check: sum of degrees = 4 × 3 = 12 = 2 × 6 ✓
  5. Understanding Graph with edges PQ, PR, QR, QS, RT, ST, TU, SU. Adjacency matrix and degrees.
    Degrees: deg(P) = 2, deg(Q) = 3, deg(R) = 3, deg(S) = 3, deg(T) = 3, deg(U) = 2
    Sum = 16 = 2 × 8 edges ✓

    Adjacency matrix:
    PQRSTU
    P011000
    Q101100
    R110010
    S010011
    T001101
    U000110
  6. Understanding Connected graph with 7 vertices that is a tree. How many edges?
    A tree with n vertices always has exactly n − 1 edges.
    For n = 7: 6 edges

    Justification: A tree is a connected graph with no cycles. Adding a cycle would require an extra edge that creates redundancy. You can prove by induction: a tree with 1 vertex has 0 = 1 − 1 edges. Each time you add a vertex to a tree, you add exactly one edge to connect it. So n vertices requires n − 1 edges.
  7. Understanding Adjacency matrix for 4-vertex graph. Edge list and degrees.
    Reading the upper triangle of the matrix (to avoid counting each edge twice):
    Edges: AB, AC, BC, BD, CD

    Degrees:
    deg(A) = 2 (row A sum: 0+1+1+0 = 2)
    deg(B) = 3 (row B sum: 1+0+1+1 = 3)
    deg(C) = 3 (row C sum: 1+1+0+1 = 3)
    deg(D) = 2 (row D sum: 0+1+1+0 = 2)

    Check: 2 + 3 + 3 + 2 = 10 = 2 × 5 edges ✓
  8. Understanding Road network A–B (12), A–C (8), B–C (5), B–D (10), C–E (15), D–E (6).
    (a) 6 edges (listed above)
    (b) Degrees: deg(A) = 2, deg(B) = 3, deg(C) = 3, deg(D) = 2, deg(E) = 2. B and C both have the highest degree (3).
    (c) Yes, the graph is connected. From any town you can reach any other: e.g. A→B→D→E; A→C→E; etc.
  9. Problem Solving 5 vertices with four degrees 1, 2, 3, 4. Find the fifth degree.
    The sum of all degrees must be even (= 2 × number of edges).
    1 + 2 + 3 + 4 + x = even
    10 + x = even → x must be even

    In a simple graph with 5 vertices, the maximum degree is 4 (connected to all others).
    Possible even values: 0, 2, or 4.

    However, if degree 4 is already taken (one vertex connects to all others), then the vertex with degree 0 would be isolated — but then the degree-4 vertex cannot connect to all 5 others (it could only reach 4). This means the vertex with degree 4 is connected to all others including the degree-0 vertex, which is a contradiction.

    The fifth degree can be 0 (isolated, but creates contradiction with deg-4 vertex — so deg-4 vertex must connect to all, meaning the “0” vertex is not isolated; this is impossible), 2 (most likely valid), or 4 (two vertices of degree 4 both connect to all others — possible). Careful analysis: x = 2 or x = 4 are both mathematically possible.
  10. Problem Solving 3-regular graph on 6 vertices.
    (a) Number of edges:
    Sum of degrees = 6 × 3 = 18 = 2 × |E| → |E| = 9 edges

    (b) 3-regular graph on 5 vertices:
    Sum of degrees = 5 × 3 = 15. But the sum of degrees must be even (= 2 × |E|). 15 is odd, which is impossible. So no 3-regular simple graph on 5 vertices can exist. (A k-regular graph on n vertices requires kn to be even.)

    (c) One possible 3-regular graph on 6 vertices (A, B, C, D, E, F):
    Edges: AB, AC, AD, BC, BE, CF, DE, DF, EF
    Degrees: A=3, B=3, C=3, D=3, E=3, F=3 ✓

    (There are multiple valid answers; the “prism graph” is a well-known example: two triangles ABC and DEF connected by AD, BE, CF.)

← Back to Questions