Trees

1.[1p]

How many labelled trees are there on the vertex set $\{1,2,3,4,5,6\}$?

2.[2p]

A tree has three vertices of degree $3$, two vertices of degree $4$, and every other vertex is a leaf. How many leaves does it have?

3.[1p]

A forest has $40$ vertices and $7$ connected components. How many edges does it have?

4.[2p]

Two triangles share a single vertex: the graph has vertices $a,b,c,d,e$ and edges $ab$, $bc$, $ca$, $ad$, $de$, $ea$. How many spanning trees does it have?

5.[2p]

What is the Prüfer code of the path on $\{1,2,3,4,5\}$ that visits the vertices in the order $3,1,4,2,5$?

6.[2p]

A labelled tree on $\{1,\dots ,9\}$ has Prüfer code $2,2,5,5,5,7,7$. How many leaves does it have?

7.[3p]

How many labelled trees on $\{1,\dots ,7\}$ have vertex $1$ as a leaf?

8.[1p]

How many different binary trees have exactly $5$ internal vertices (each vertex having either no children or a left and a right child)?

9.[2p]

A graph $G$ has $n$ vertices. Which of these conditions guarantee that $G$ is a tree?

Select all that apply