# If G is connected, and has two spanning trees, … a) Prove that $H$ has a vertex $v$ with deg($v$)$\leq$ 3.

• Is this a proof by contradiction, so assume deg($v$) >= 4, then by Handshaking Theorem, 2|E(H)| $\geq$ $4*p$. Since there are two spanning trees, with each one having $p-1$ edges, by definition, then $E(T_1)\cup E(T_2) \leq 2*p-1$. Now, since there is a contraction since $4*p$ $!= 2*p-1$.
• Is this how the proof is suppose to go? What can I assume when I have two spanning trees in G?

b) Give an example of $G$, $T_1$ and $T_2$ in which every vertex $H$ = $T_1$ $\cup$ $T_2$ has degree of at least 3.

• Don't know how to draw this.

c) Prove that if $E(T_1)\cap E(T_2)$ = $\emptyset$, and $T_1$ and $T_2$ each have a vertex of degree more than $p/2$, then $H$ has a vertex of degree exactly 2.

• So $E(T_1)\cap E(T_2)$ means that $T_1$ and $T_2$ are the same tree, since they don't share any edges. But how do I prove this?

• How do you reckon that $E(T_1)\cap E(T_2)=\emptyset$ implies that $T_1$ and $T_2$ are the same? You said it your self, they don't share any edges. In what sense could they then be considered the same tree? – Paddling Ghost Aug 1 '17 at 4:45

a) Handshaking shows $2|E(H)| \ge 4p$. Each spanning tree has $p-1$ edges so $|E(H)| \le 2p-2$. Thus $2p \le 2p-2$ which is a contradiction.
b) Let $G$ be the complete graph on $4$ vertices. Let $T_1$ and $T_2$ be spanning trees with no common edges. Then $H=G$.
Hint 1: The only way for $H$ to have a vertex of degree $2$ is if this vertex is a leaf in both trees. (This is because both trees are spanning and share no edge.)
Hint 2: Each tree has $> p/2$ leaves.