A network is a collection of points and lines between the points. The points are called vertices and the lines which connect them are called edges. Each edge has a vertex at each end.
Here are some possible networks:
A connected network is a network in which we can get from any vertex to any other by travelling along the edges.
A planar network is one where no edges cross each other.
A cyclic network is one where there is a closed circuit or loop somewhere in the network. A network with no closed circuits is an acyclic network.
Describe each of the networks above with the words connected/disconnected, planar/non-planar and cyclic/acyclic.
The only combinations of properties that have not been drawn above are:
Can you draw networks satisfying these conditions?
A network is called a tree if it is connected, planar and acyclic (like network 5 above).
Investigate the number of edges in trees with different numbers of vertices.
Can you prove a relationship between the number of vertices in a tree and the number of edges?
There are two different trees which have 4 vertices.
Note that the following two trees do not count as different as we can stretch each of them out as a straight line.
How many different trees can you draw with 5 vertices?
The degree of a vertex is the number of edges that meet at the vertex.
Draw all the possible trees with 2, 3 and 4 vertices.
Label the vertices on your drawings with the degree of each vertex.
Do the same for your trees with 5 vertices.
What can you say about the sum of the degrees of the vertices in trees with 2, 3, 4, 5, ... $n$ vertices?
Can you explain what you have noticed?
How many different trees can you draw with 6 vertices?
How many trees can you draw with 7 vertices?
How can you use your results so far to convince yourself that you have found all of the possible trees?