CMI2017-B-5

Question

An undirected graph is $\text{connected}$ if, for any two vertices $\{u, v\}$ of the graph, there is a path in the graph starting at $u$ and ending at $v$. A tree is a connected, undirected graph that contains no cycle.

1. A $\text{leaf}$ in a tree is a vertex that has degree $1$. Prove that if $G$ is a tree with at least two vertices then $G$ contains at least two leaves.
2. A $\text{bipartite graph}$ is one in which the vertex set $V$ can be partitioned into two disjoint sets $V_1$ and $V_2$ so that for every edge $\{u, v\}$, $u$ and $v$ lie in different partitions—that is, $u \in V_1$ and v$ \in V_2$ or vice versa. Prove that if $G$ is a tree with at least two vertices, then $G$ is bipartite.

Answer 1

Attaching a proof different from the one given in the solution

Answer 2

$(a)$ Let us assume that G is a tree vertices $\geq$ 2

Trying to prove by contradiction we will assume that G does not contain atleast 2 leaves. Hence in G there are no leaves or 1 leaf.

Then, degree sum of graph $\geq$ $2(n-1) + 1$

or, $\sum_{v = 1}^{n} deg(v) \geq 2n - 1$

By handshaking lemma, 

Number of edges $\geq \large \frac{2n - 1}{2}$

or, 

Number of edges $\geq \large n - \frac{1}{2}$

But we know that maximum edges in a tree with n nodes can be $n-1$.

This means our assumption of of G containing less than 2 leaf nodes is incorrect.

---

$(b)$ Assuming G is a tree with n vertices with $n \geq 2$

We know that every vertex of a bipartite graph can be partitioned into two disjoint sets $V_{1}$ and $V_{2}$ so that every vertex of $V_{1}$ can be colored with same color and also every vertex of $V_{2}$ can be colored with another color.

Select any vertex $v$ from G. Place the vertices that are an odd distance from $v$ in $V_{1}$ and those that are an even distance from v in $V_{2}$. Clearly any two distinct vertices from $V_{1}$ are not adjacent by an edge, and likewise for $V_{1}$, because trees have no circuits; moreover, $V_{1}$ $V_{2}$ clearly partition the vertex set of the graph into two disjoint subsets. Thus, any tree is bipartite.

Answer 3