Trees and spanning trees practice questions | General Mathematics (Year 12, VCE Units 3 & 4, Graphs and networks, Trees and minimum connectors)

Trees and spanning trees

A tree is connected and has no cycles, loops or parallel edges. A spanning tree also includes every vertex of the source graph and has the required number of edges

e=n-1

Use n minus 1 edges A tree with n vertices has exactly n - 1 edges \(\displaystyle n=6\Rightarrow e=6-1=5\)
Check connection and cycles The edge set must be connected and contain no cycle, loop or parallel edge \(\displaystyle n=5,\quad e=4,\quad \text{connected and no cycle}\)
Check every source vertex A spanning tree uses all vertices in the source graph \(\displaystyle V_{\text{candidate}}=V_{\text{source}}\)
Count removals and length Remove e - (n - 1) source edges and add the weights of all retained tree edges \(\displaystyle 8-(6-1)=3,\quad 4+7+6+5+3=25\,\text{km}\)

Worked example

A network has 6 sites and 8 connections. A proposed spanning tree uses five edges with lengths 4 km, 7 km, 6 km, 5 km and 3 km. Find how many connections must be removed and find the length of the spanning tree

n=6,\quad e=8,\quad 4+7+6+5+3\,\text{km}

\(\displaystyle n-1=6-1=5\)A spanning tree on 6 sites retains 5 edges
\(\displaystyle 8-5=3\)The network must lose 3 connections to retain 5 edges
\(\displaystyle 4+7+6+5+3=25\,\text{km}\)Add the weights of all five retained edges
\(\displaystyle 3\text{ connections removed},\quad 25\,\text{km}\)The spanning tree is formed after 3 removals and has length 25 km

Common mistakes

Using n edges instead of n - 1

✕\(\displaystyle n=6\Rightarrow e=6\quad\text{for a tree}\)✓\(\displaystyle n=6\Rightarrow e=6-1=5\quad\text{for a tree}\)

A tree with n vertices has n - 1 edges, so using n edges adds a cycle

Missing a source vertex

✕\(\displaystyle V_{\text{candidate}}=\{A,B,C,D,E\}\subsetneq V_{\text{source}}=\{A,B,C,D,E,F\}\Rightarrow\text{spanning tree}\)✓\(\displaystyle V_{\text{candidate}}=V_{\text{source}}=\{A,B,C,D,E,F\}\)

A spanning tree must include every vertex of the source graph, not only the vertices touched by the chosen edges

Leaving out a tree edge from the length

✕\(\displaystyle 4+7+6+5=22\,\text{km}\)✓\(\displaystyle 4+7+6+5+3=25\,\text{km}\)

The length of a spanning tree is the sum of every retained edge weight

Difficulty levels

introRecognise a tree among candidate graphs using connection, cycle and edge-count checks

standardIdentify a spanning tree and calculate how many source edges are removed

challengeCalculate the length of a weighted spanning tree and detect a hidden cycle candidate

examSelect a spanning tree or an edge count from computed candidate values

Questions about this topic

What makes a graph a tree?+

A tree is connected and has no cycles, loops or parallel edges. If it has n vertices, it has n - 1 edges

What is a spanning tree?+

It is a tree formed from a connected graph that includes every vertex of the original graph

Is every spanning tree a minimum spanning tree?+

No. A minimum spanning tree is the spanning tree with the least total weight. Other spanning trees can have greater total weights

Can I use a calculator?+

A calculator is allowed unless a question is marked no calculator

Which year level and chapter is this?+

Year 12, VCE Units 3 & 4, General Mathematics, chapter 13: Graphs and networks

In this chapter

Count the vertices, edges and loops of a graph Degrees, the degree sum, and even and odd vertices Graph types, subgraphs, connection models and method selection Connected graphs and bridges Identify isomorphic graphs Planar graphs and drawings in planar form Faces and Euler's formula Represent a network in a matrix Identify the network a connection matrix describes Classify a route: walk, trail, path, circuit or cycle Eulerian trails and circuits: existence and identification Hamiltonian paths and cycles Read a weighted graph The shortest path by inspection Dijkstra's algorithm for shortest distances and routes Trees and spanning trees Minimum spanning trees by Prim's and Kruskal's algorithms A full network investigation