You may also like

problem icon

Modular Fractions

We only need 7 numbers for modulus (or clock) arithmetic mod 7 including working with fractions. Explore how to divide numbers and write fractions in modulus arithemtic.

problem icon

Power Quady

Find all real solutions of the equation (x^2-7x+11)^(x^2-11x+30) = 1.

problem icon

Areas and Ratios

Do you have enough information to work out the area of the shaded quadrilateral?

Tree Graphs

Age 16 to 18 Challenge Level:

The simplest tree graph consists of one line with two vertices, one at each end.

If a new line is added it must connect to one and only one of the existing vertices.

If the new line connected to no vertices, the tree graph would not be connected, as the new line's vertices could not be reached from the existing vertices.

If each end of the new line connects to a vertex the graph will have a circuit and will not be a tree graph.

So every new line added will join on to one existing vertex and create a new vertex at its end. This adds one line and one vertex to the tree graph making no change to the difference between the numbers of edges and vertices. So the difference remains constant at what it originally was.

Marcos's solution is a subtle variation on the above method:

  1. Firstly, it's obvious that every edge is connected to exactly two vertices. (by definition)
  2. More importantly, there is at least one vertex which is connected to exactly one edge.

Proof . If there wasn't at least one such vertex we could keep moving around the graph indefinitely and as there is a finite number of edges it would mean that there is a cycle, counter to the definition of a tree.

Take one such vertex as described in (2) and its respective edge. So far we have 2 vertices and 1 edge. The difference is 1.

(*) Add to this an adjacent edge (this is adding one edge and one vertex. The difference is still one.

Generally, carrying out this step, (*), an arbitrary number of times until we add the final edge will still result in a difference of 1 (as the step was in no way linked to fact that the previous edge was the starting one)

Hence, the number of vertices is one more than the number of edges.