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.