You may also like

problem icon

Shape and Territory

If for any triangle ABC tan(A - B) + tan(B - C) + tan(C - A) = 0 what can you say about the triangle?

problem icon

Napoleon's Hat

Three equilateral triangles ABC, AYX and XZB are drawn with the point X a moveable point on AB. The points P, Q and R are the centres of the three triangles. What can you say about triangle PQR?

problem icon

The Root Cause

Prove that if a is a natural number and the square root of a is rational, then it is a square number (an integer n^2 for some integer n.)

Tree Graphs

Stage: 5 Challenge Level: Challenge Level:1

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.