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.Higher 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, called vertices. Undirected: each edge is a two-way link, like a road, not a one-way street.
  • What is fixed? The edges AB, BC and CD, and only those: no AC, no BD, no AD. No weights are given, so nothing gets added up.
  • What do they want? Yes or no: is this graph itself a spanning tree? Then explain: show each condition holds or fails.
Céim

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

Trees & Spanning Trees

A tree is connected and acyclic, and a spanning tree contains every vertex of the original graph.

Why it matters

In exam network problems, counting edges alone can overlook isolated vertices and cycles.

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, called vertices. Undirected: each edge is a two-way link, like a road, not a one-way street.
    • What is fixed? The edges AB, BC and CD, and only those: no AC, no BD, no AD. No weights are given, so nothing gets added up.
    • What do they want? Yes or no: is this graph itself a spanning tree? Then explain: show each condition holds or fails.
  2. Understand

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

    • Which settles whether it is a spanning tree? All three tests?: Every vertex included, connected and no cycle. Each can fail on its own, so all three must be shown.
    • Where do I start?
    • Count first: n vertices, m edges. A tree on n vertices always has n − 1 edges. That is a quick check, not the proof.
  4. Solve

    • Is every vertex in, and is it connected?
    • Why one route is enough: if a single route visits every vertex, any two vertices are joined along it.
    • n = 4 vertices, m = 3 edges.
  5. Check

    • Is it right?
    • Remove each edge
    • Remove AB: A is cut off from B, C, D.