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?
Thanks in advance.