enter image description here

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.

  • $\begingroup$ 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? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.