You may also like

problem icon

Rotating Triangle

What happens to the perimeter of triangle ABC as the two smaller circles change size and roll around inside the bigger circle?

problem icon

Doodles

A 'doodle' is a closed intersecting curve drawn without taking pencil from paper. Only two lines cross at each intersection or vertex (never 3), that is the vertex points must be 'double points' not 'triple points'. Number the vertex points in any order. Starting at any point on the doodle, trace it until you get back to where you started. Write down the numbers of the vertices as you pass through them. So you have a [not necessarily unique] list of numbers for each doodle. Prove that 1)each vertex number in a list occurs twice. [easy!] 2)between each pair of vertex numbers in a list there are an even number of other numbers [hard!]

problem icon

Russian Cubes

How many different cubes can be painted with three blue faces and three red faces? A boy (using blue) and a girl (using red) paint the faces of a cube in turn so that the six faces are painted in order 'blue then red then blue then red then blue then red'. Having finished one cube, they begin to paint the next one. Prove that the girl can choose the faces she paints so as to make the second cube the same as the first.

Tree Graphs

Stage: 4 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.