Network Trees

Why do this problem?
In introducing the idea of networks and graph theory this is one of the simplest results to prove. It gives learners practice in mathematical reasoning and an idea of what graphs are.
This problem can be used with KS4 students as an introduction to some of the topics covered in A-level Further Maths.
It can also be used as an introduction to the idea of induction (If we know that a graph with $n$ vertices has $n-1$ edges, what happens if we add an extra vertex?)


Possible approach
The idea of a network could be introduced through an example of connections between people (perhaps using the idea of "six degrees of Kevin Bacon" and linking some actors together via films that they have both starred in).  Other real life networks, such as the London Undergorund Map, could be discussed.

You could also introduce alternative terms for some of the ideas introduced: graph for network, arc for edge, and node for vertex should be mentioned. 

Consider the six given graphs and decide whether each one is connected/disconnected, planar/non-planar and cyclic/acyclic.  Students could draw other networks which satisfy various conditions or could consider how the given graphs could be altered to make them connected, planar and acyclic.

Key questions

• What is the simplest network you can draw?
• Draw trees for networks with 1, 2, 3, 4, ... vertices.  How many edges are needed?  
• Does every tree for a network of 5 vertices have the same number of edges?
• Can you write down a rule connecting the number of edges and the number of vertices?
• If we add an extra vertex to a network, what happens to the number of edges?  If we add an edge to a network, what happens to the number of vertices.

Possible support
Simply Graphs gives an introduction to networks where students can think about how they would categorise networks before being introduced to the definitions in this problem.
Learners might spend a little time playing the game Sprouts. Sprouts leads to much more graph theory than this one problem, and you can read more in the Sprouts Article.

Possible extension
The connections between networks and polyhedra, and a justification of Euler's Theorem, can be found in this problem.
Try the problem Plum Tree.