Tree Graphs

Why do this problem?
In introducing the idea of graph theory this is about the simplest result to prove. It gives learners practice in mathematical reasoning and an idea of what graphs are. This problem also links to a set of interesting problems on Magic Graphs.No prior knowledge of graphs is needed to prove this result.

Possible approach
The question provides a definition of a graph. The alternative words: network for graph, arc for edge and node for vertex should be mentioned. The first step is for a discussion of graphs with some examples (e.g. London underground map). The learners should draw some graphs and decide which are connected, which not connected, which are trees and which are not trees. They should count the edges and vertices in each of the trees and talk about how to prove this general result.

Key questions
Is a line segment a graph? Explain why or if not, why not.

Is a single point a graph. Explain why or if not, why not.

When you start drawing a graph, what is the simplest graph you can draw?

What happens to the numbers of vertices and edges at each stage as you draw the graph if you make sure that the drawing at each stage represents a graph?

Possible support
Leaners might spend a little time reading the article Sprouts and playing the game. Sprouts leads to much more graph theory than this one problem.

Possible extension
Try the problem Plum Tree.