01204211/homework9 graph theory 2

This is part of 01204211-58

Due: 18 Dec 2015

H.1 (LPV-7.3.9) Prove that at least one of $G$ and ${\bar {G}}$ is connected. (Note that ${\bar {G}}$ is a complement graph of $G$.)

H.2 TBA There is no problem H.2. Please skip this problem.

H.3 (LPV-8.3.2) How many labeled trees on n nodes are stars? How many are paths?

H.4 (LPV-8.5.4) Prove that if a tree has a node of degree d, then it has at least d leaves.

H.5 (LPV-10.3.1) In class, we proved the Hall's marriage theorem. In this problem, you will show that if a bipartite graph $G=(A\cup B,E)$ satisfies the condition that every node has the same degree $d\geq 1$, the $G$ has a perfect matching.

(Hint: first prove that (1) $|A|=|B|$, and (2) for any subset $X\subseteq A$ of size $k$, the number of nodes in $B$ that are connected to some node in $X$ is at least $k$, then apply the Hall's theorem.)

H.6 (LPV-10.4.9) Let G be a bipartite graph with m nodes on both sides. Prove that if each node has degree larger than m/2, then it has a perfect matching.

(Hint: prove that G is good. Is is possible to find a subset of nodes on the left side that violates condition (2) for the Hall's marriage theorem?)