Trees

Which of the following graphs are trees?

1. $G = (V, E)$ with $V = \{a, b, c, d, e\}$ and $E = \{\{a, b\}, \{a,e\}, \{b, c\}, \{c,d\}, \{d,e\} \}$

2. $G = (V, E)$ with $V = \{a, b, c, d, e\}$ and $E = \{\{a, b\}, \{b, c\}, \{c,d\}, \{d,e\}\}$

3. $G = (V, E)$ with $V = \{a, b, c, d, e\}$ and $E = \{\{a, b\}, \{a, c\}, \{a,d\}, \{a,e\}\}$

4. $G = (V, E)$ with $V = \{a, b, c, d, e\}$ and $E = \{\{a, b\}, \{a, c\}, \{d,e\}\}$

For each degree sequence below, decide whether it must always, must never, or could possibly be a degree sequence for a tree. Remember, a degree sequence lists out the degrees (number of edges incident to the vertex) of all the vertices in a graph in non-increasing order.

1. $(4,1,1,1,1)$

2. $(3,3,2,1,1)$

3. $(2,2,2,1,1)$

4. $(4, 4, 3, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1, 1)$

If a graph $G$ with $v$ vertices and $e$ edges is connected and has $v \lt e+1$, must it contain a cycle? Prove your answer.

Unless it is already a tree, a given graph $G$ will have multiple spanning trees. How similar or different must these be?

1. Must all spanning trees of a given graph be isomorphic to each other? Explain why or give a counterexample.

2. Must all spanning trees of a given graph have the same number of edges? Explain why or give a counterexample.

3. Must all spanning trees of a graph have the same number of leaves…