I'm trying to prove that trees are bipartite by induction. Below is what I've come up with.
Let $T$ be a tree. If it has no edges, it is bipartite (one can choose the vertex to be in the set $A$, $B$ to be the empty set, and then for every edge in the edge set, the claim is satisfied vacuously, so $(A,B)$ is a bipartition of $T$). Assume that all trees $T$ with fewer than $m$ edges are bipartite, where $m\geq 1.$ Let $T$ be a tree with $m$ edges. If $m=1$, then there are $2$ vertices of $T$ and we can let each one be in a different set of a bipartition. So we may assume $m>2.$ Let $e = uv$ be an edge of $T.$ Then $e$ is a bridge, so $T-e$ has exactly two components, $T_1$ and $T_2,$ both of which have fewer than $m$ edges and thus by the inductive hypothesis are bipartite. Let $(A_i,B_i)$ be bipartitions for $T_i, 1\leq i\leq 2.$ Then $(A_1\cup B_2, A_2\cup B_1)$ is a bipartition of $T.$ Indeed, let $w = ab$ be an edge of $T$ other than $e.$ Then $a$ is in $A_1\cup B_1\cup A_2\cup B_2,$ by the construction of the $A_i$'s and $B_i$'s. If $a\in A_1,$ then $b\not \in B_2$ as otherwise there would be an edge from a vertex in $T_1$ to one in $T_2,$ which contradicts the fact that $T_1$ is connected in $T-e$. Also $b\not \in A_1$ as $(A_1, B_1)$ is a bipartition of $T_1$ so there are no edges with both ends in $A_1$ in $T_1,$ and so there are no edges with both ends in $T$, since $T_1$ is a subgraph of $T$ that contains all the vertices in $A_1$. Similarly, if $a \in B_2, b \not \in A_1,$ if $a\in A_2, b\not \in B_1,$ and if $a \in B_1, b\not \in A_2.$ Thus every edge connects a vertex in $A_1\cup B_2$ to a vertex in $A_2\cup B_1,$ so $(A_1\cup B_2, A_2\cup B_1)$ is a bipartition and $T$ is bipartite.
Is this incorrect?
Best Answer
The general idea will work, even though you forgot to mention why the edge $e$ isn't causing you any problems (for example if $u$ and $v$ are both in $A_1\cup B_2$).
A hint for a different, maybe easier approach - prove this by induction, but instead of using a random bridge, use the fact that every tree has a leaf, and remove it.