Step 1 of 8 · Worked example · TEACH

← Algorithms, Optimisation & Project Scheduling

0 of 3 done

Work through the example to CHECK to open the problems.

Reach CHECK to open the problems.Ordinary Level · Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 1

Follow the worked example and explain why each modelling and calculation step is valid.

A simple undirected graph has vertices A,B,C,D and exactly edges AB, BC, CD. Is it a spanning tree? Explain.

An undirected graph has vertices A, B, C and D. Its only edges are AB, BC and CD.

Is it a spanning tree? Explain.

Read it once, slowly. Then copy it onto your page.
  • What is going on? Four points, A, B, C and D. Each point is a vertex. Undirected: every edge works both ways, like a two-way road.
  • What is fixed? Three edges, AB, BC and CD, and only those. There is no AC, no BD and no AD.
  • What do they want? Yes or no: is it a spanning tree? Then explain: give the reason, not just the answer.
Céim

Ordinary Level Applied Maths · Algorithms, Optimisation & Project Scheduling · Step 1 of 8

Trees & Spanning Trees

A tree is connected and has no cycles, and a spanning tree connects every vertex of the original graph.

Why it matters

Spanning trees let you remove unnecessary network links while keeping every vertex reachable.

The worked example

An undirected graph has vertices A, B, C and D. Its only edges are AB, BC and CD. Is it a spanning tree? Explain.

How the worked example goes

  1. Read

    • What is going on? Four points, A, B, C and D. Each point is a vertex. Undirected: every edge works both ways, like a two-way road.
    • What is fixed? Three edges, AB, BC and CD, and only those. There is no AC, no BD and no AD.
    • What do they want? Yes or no: is it a spanning tree? Then explain: give the reason, not just the answer.
  2. Understand

    • How do I picture it?
    • Put four dots on your page: A, B, C, D.
    • Draw one line for each edge: A to B, B to C, C to D. Draw no others.
  3. Reduce

    • Which settles whether it is a spanning tree? All three tests pass: Every vertex in, connected and no cycle. Each one can fail on its own, so show all three.
    • Where do I start?
    • Count: 4 vertices, 3 edges. A tree on 4 vertices always has 4 − 1 = 3 edges. That is a check, not the proof.
  4. Solve

    • Is every vertex in? Can I get everywhere?
    • Vertices: A, B, C, D. All 4 are in. ✓
    • Start at A. AB to B, BC to C, CD to D.
  5. Check

    • Is it right?
    • Count: 3 edges = 4 − 1. ✓
    • Take away any one edge and the graph splits in two. Take away AB: A is alone. So no edge is spare. ✓