Lesson 1: Trees and spanning trees

Counting the spanning trees of a small graph

SkillTrees and spanning trees

Worked example

  • Complex familiar
  • Technology free

Graph GG has vertices AA, BB, CC and DD and five edges: ABAB, BCBC, CDCD, DADA and the diagonal ACAC.

(a) How many edges does a spanning tree of GG have?

(b) How many edges must be removed from GG to leave a spanning tree?

(c) How many different spanning trees does GG have?

1 of 5 steps
  1. Step 1: Use the edge count of a tree

    GG has v=4v = 4 vertices, so every spanning tree has v−1=3v - 1 = 3 edges.

    3 edges3 \text{ edges}

Try a similar one

A fresh question of the same kind, checked as you answer, with hints and a full solution.

Method

  1. A spanning tree of a graph with vv vertices has v−1v - 1 edges.

  2. To count spanning trees of a small graph, list every set of v−1v - 1 edges and cross out those containing a cycle.

Watch out for

  • Forgetting that a spanning tree must include DD: the subgraph ABAB, BCBC, ACAC has 3 edges but is a cycle and misses DD.

Save your progress with a free account