This question is similar to Is every forest with more than one node a bipartite graph?, but requires a proof by induction.
This was a past exam question.
–
Let P(G) be the predicate that graph G=(V,E) is bipartite, and can be partitioned into G=($V_1,V_2$,E) s.t. $V_1 \lor V_2 = V$, and $\forall e \in E$, e joins a node from $V_1$ and one from $V_2$. (Note the definition we have learnt does not consider a bipartite graph as one with no odd cycles, so unless I prove that first it wouldn't be acceptable. I chose to try to prove it using the definition given)
Basis step:
A forest is any acyclic graph. Clearly, a forest with 1 or 2 nodes (or any amount of edges) and no edges is bipartite, since there is no restriction on how we define $V_1, V_2$ in this case. So consider the forest with 2 nodes and 1 edge, for example A $\rightharpoonup$ B. This can clearly be partitioned into {A} and {B}, and its only edge will join nodes from these two sets.
–
Inductive step:
Since bipartite only places a restriction on classification based on edges, nodes with degree of 0 (no adjacent nodes/no edges) do not affect whether a graph is bipartite.
Assume that some forest is bipartite. Consider the forest formed by removing all such nodes of degree 0 from that forest.
Now, we need to prove that adding an arbritary edge to that forest, such that the resulting graph is still a forest (the new edge doesn't form a cycle), results in a bipartite graph.
Then this edge requires that either 2, 1 or 0 nodes be added to the graph. These nodes may already have been nodes of degree 0 in the known bipartite forest, so specifically, this edge requires that either 2, 1 or 0 new nodes have their classification restricted by the definition of bipartite. Since the effect on the graph is the same, we can call this operating adding a node.
If 2 new nodes are added to accomodate the new edge, then we can classify them such that they are in different partitions. The graph is still bipartite.
If 1 new node was added, then we have a new edge that joins a classified node and an unclassified node. The unclassified node is only joined to one edge, so it can be classified such that it is in the other partition to the classified node on the same edge. The graph remains bipartite.
—
This is where I got stuck. I thought that restricting the forest to ignore nodes with degree 0 would ensure that any new edge required at least one node. That is not true, however, since if we had two connected components:
A $\rightharpoonup$ B, C $\rightharpoonup$ D,
partitioned such that $V_1$ = {A,C}, $V_2$ = {B,D}, then this is bipartite. It would not create a cycle to add an edge A $\rightharpoonup$C, however, since B and D are not connected. So the result would still be a cycle.
Clearly, this would be an edge between two members of $V_1$, so a re-partitioning would be required. I'm not sure how to prove that that re-partitioning is always possible.
Best Answer
I think this is all unnecessarily complicated. You can use induction over the number of edges, without removing edgeless nodes.
Basis step: A forest without edges is bipartite.
Inductive step: Assume all forests with $k$ edges are bipartite. Given a forest $F$ with $k+1$ edges, remove an edge $e$ and find a bipartition of the resulting forest $F'$ with $k$ edges. The removed edge $e$ of $F$ connects two trees in $F'$. If the vertices it connects are in the same class, flip the class of all nodes in one of the two trees. Since there are no edges between the nodes of the tree and other nodes, this again results in a valid bipartition. Now the two nodes of $e$ are in different classes, so adding $e$ back in doesn't invalidate the bipartition.