Network Trees

Age 14 to 18

Challenge Level Yellow star

Nayanika from The Tiffin Girls' School in the UK sent in a solution which is an excellent start to this difficult problem. Click here to see Nayanika's solution with some notes about how the solution could continue.

John from Calthorpe Park Fleet in the UK built on Nayanika's ideas. Click to see John's solution.

Click twice on the images to enlarge them.

Below the rest of John's solution is a rigorous proof that the number of edges in a network tree is 1 less than the number of vertices, submitted by Teiva. This is the rest of John's work:

Teiva sent in a proof that a network tree with $n$ vertices has $n-1$ edges. Teiva's proof has two parts.

Part A: Prove that every tree contains at least two vertices of degree 1

Part B: Use Part A and proof by induction to prove that a tree with $n$ vertices has $n-1$ edges

This is a more detailed structure of Teiva's proof. Click to see the Teiva's work for each step/stage.

Part A (lemma): Proof that every tree contains at least two vertices of degree 1, using the strong principle of induction

1. Check that the statement is true when $n=2$

2. Assume that the statement is true when $n=2,3,4,...,k$ for some whole number $k,$ and use this assumption to prove that the statement is true when $n=k+1$

take a tree with $k+1$ vertices and select one of those vertices. If $d$ is the order of the vertex, then the vertex is connected to $d$ sub-networks via its $d$ edges.

Prove that the $d$ sub-networks are all separate to each other and are all trees or single vertices

Firstly, we note that there can be no connection between any two of these sub-networks, other than through V. This is because, by definition, every vertex within each sub-network has a connected path to each other vertex in the subnetwork. This means each sub-network is connected, and so any connection between two of these sub-networks, aside from the pre-existing one through V, would result in a cycle inside T, which is impossible because T is a tree. Hence, eachsub-network is distinct from the others (and indeed they were earlier drawn as such. This justifies the drawing) (It should be noted that any of the sub-networks might be a single vertex, and indeed the above section is only strictly accurate if we take the single vertex as a connected network, which I shall do).

Secondly, we note that each sub-network is acyclic, as it is a sub-network of a tree (which is acyclic).

Hence, and using the previous point, each sub-network is either a lone vertex, or it is a tree.

Use the assumption to prove that the network has at least two vertices of degree 1

Let the number of such sub-trees be denoted by $t$ and the number of lone vertices be denoted by $l$. Since each sub-tree is distinct from the others, we have that $t+l=d$ (recalling that $d$ is the degree of V).

Now, by the inductive hypothesis, each of these sub-trees contains at least 2 vertices of degree 1. Then either one of these is the explicitly drawn vertex (which is connected to V and is hence not a vertex of degree 1 in T), or not. In either case, a sub-tree contributes at least one vertex of degree 1, so that at least $t$ vertices of degree 1 are contributed to T. We can then note that if some sub-network is a lone vertex, then it is a vertex of degree 1.

Then if $d\ge2,$ our lemma is true for T. Otherwise (i.e. if $d=1$) then we note that V is itself a vertex of degree 1 to T, so that our lemma is true for T.

Hence since $d\ge1$ (because T is connected), our lemma is true for T and hence for any tree of $k+1$ vertices, so that our inductive argument is complete.

3. Conclude that this means the statement must be true for all whole numbers

Teiva has proved that trees with 2 vertices have at least 2 vertices of degree 1. Teiva has also proved that a tree with $k+1$ vertices has at least 2 vertices of degree 1, as long as all trees with fewer than $k+1$ vertices have at least 2 vertices of degree 1. This means that you could use the fact that trees with 2 vertices have 2 vertices of degree 1 to prove that all trees with 3 vertices have at least 2 vertices of degree 1. Then you could use those two facts to prove that all trees with 4 vertices have at least 2 vertices of degree 1. Then you could use those facts to prove it for trees with 5 vertices, and then trees with 6 vertices, and so on. Because this goes on forever, Teiva has proved that all trees with any number of vertices have at least 2 vertices of degree 1.

That is, every tree contains at least two vertices of degree 1.

Part B: Proof that a tree with $n$ vertices has $n-1$ edges, using Part A and the weak principle of induction

1. Check that the statement is true when $n=2$

It is then (very) trivially established that every tree contains a vertex of degree 1. We then use weak induction to prove that every tree of $n$ vertices contains exactly $n-1$ edges. This theorem is true for trees of 2 vertices, as the only such tree consists of 2 vertices connected by 1 edge (as established).

2. Assume that the statement is true when $n=k$ for some whole number $k,$ and use this assumption to prove that the statement is true when $n=k+1$

Now, assume that the theorem is true for all trees of $k$ vertices, for some $k$ with $k\ge2,$ and consider a tree of $k+1$ vertices. By our lemma, this tree (call it T) may be drawn as follows:

We investigate the sub-network structure:

Firstly, it is connected, as T is connected, and the extra vertex in T clearly does not create any new paths between vertices in the sub-network.

Secondly, it is acyclic, as it is a sub-network of a tree.

Hence, the sub-network is a tree, and is indeed clearly one of $k$ vertices.

Then, by the inductive hypothesis, this sub-tree contains exactly $k-1$ edges, so that T contains $(k-1)+1=(k+1)-1$ edges, and our theorem is hence true for all trees of $k+1$ vertices.

3. Conclude that this means the statement must be true for all whole numbers

Teiva has proved that trees with 2 vertices have 1 edge. Teiva has also proved that all trees with $k+1$ vertices have k edges, as long as all trees with $k$ vertices have $k-1$ edges. This means that you could use the fact that trees with 2 vertices have 1 edge to prove that all trees with 3 vertices have 2 edges. Then you could use this fact to prove that all trees with 4 vertices have 3 edges. Then you could use this fact to prove that trees with 5 vertices have 4 edges, and then you could prove that trees with 6 vertices have 5 edges, and so on. Because this goes on forever, Teiva has proved that all trees with any number of vertices, say $n$, have $n-1$ edges.

That is, it is proven that all trees of $n$ vertices contain exactly $n-1$ edges.

Teiva added a further note:

I would like to note that this is a special case of Euler's formula for planar networks ($V-E+F=2$), and so if one had that theorem, this would be a simple problem indeed. Though it is possible that this would be no simpler than what we've just done.

Also, I'm almost positive that there's an argument to be made with an infinite walk to prove that every tree has a vertex of degree 1 (or else it would be cyclic), but I just can't nail it down properly. (Why does such a walk returning to a vertex imply a cycle?)

Imagine you start off at a vertex V of a tree, and trace a path ('go for a walk') along the edges of the tree. Either the path goes on forever (an 'infinite walk'), or it eventually ends. The only way it can go on forever is either if you have found a cycle (which may or may not involve passing back through V), or if there are infinitely many vertices. In each case, the network was not a tree. Therefore the walk must end. But it must end at a vertex with only 1 edge. Therefore the tree contains a vertex of degree 1.

Number and algebra

Geometry and measure

Probability and statistics

Working mathematically

Advanced mathematics

For younger learners

Network Trees

You may also like

Fixing It

Be Reasonable

Doodles