Challenge Level

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

A

**Describe each of the networks above with the words connected/disconnected, planar/non-planar and cyclic/acyclic.**

1. Disconnected, Planar, Acyclic

2. Disconnected, Non-planar, Cyclic

3. Connected, Planar, Cyclic

4. Connected, Planar, Acyclic (note that this can be redrawn in such a way that the edges do not cross)

5. Connected, Planar, Acyclic

6. Connected, Planar, Cyclic

2. Disconnected, Non-planar, Cyclic

3. Connected, Planar, Cyclic

4. Connected, Planar, Acyclic (note that this can be redrawn in such a way that the edges do not cross)

5. Connected, Planar, Acyclic

6. Connected, Planar, Cyclic

**Draw a network which is Disconnected, Planar and Cyclic?**

**Can you draw a network which is Non-planar and Acyclic?**

A network is called a ** tree** if it is connected, planar and acyclic (like networks 4 and 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?**

What happens to the tree when you add an extra edge?

Remember that the network must not be cyclic.

Remember that the network must not be cyclic.

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? **

There are three different trees 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 do the number of vertices relate to the number of edges?

How does each edge contribute to the degrees of the vertices?

How does each edge contribute to the degrees of the vertices?

**How many different trees can you draw with 6 vertices?**

There are five different ways you can write 10 as the sum of six positive integers:

1, 1, 1, 1, 1, 5

1, 1, 1, 1, 2, 4

1, 1, 1, 1, 3, 3

1, 1, 1, 2, 2, 3

1, 1, 2, 2, 2, 2

One of these combinations produces more than one tree.

1, 1, 1, 1, 1, 5

1, 1, 1, 1, 2, 4

1, 1, 1, 1, 3, 3

1, 1, 1, 2, 2, 3

1, 1, 2, 2, 2, 2

One of these combinations produces more than one tree.

**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?**