3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A forest with one node is bipartite. $\endgroup$ – joriki Apr 9 '13 at 15:46
  • $\begingroup$ Oops, of course, since it has no edges? I would still show the A $\rightharpoonup$ B case in the basis step though, since it is the first with an edge, and thus the first that motivates making it bipartite at all. $\endgroup$ – Callum M Apr 9 '13 at 15:49
  • $\begingroup$ I think I might prefer to prove it this way: first show that any tree is bipartite. Then show that a union of disjoint bipartite graphs is bipartite. Then since a forest is a union of disjoint trees, it is bipartite. $\endgroup$ – MJD Apr 9 '13 at 17:26
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I like this a lot, I was definitely over-complicating it. Thanks! $\endgroup$ – Callum M Apr 9 '13 at 15:56
2
$\begingroup$

This seems to be an attempt at a "two dimensional" induction. This means that we no longer have a single base case.

To be consistent with your method, I think it'd be best to choose and arbitrary number of vertices $n \geq 0$, then induct on the number of edges. The base case is the $n$-vertex null graph, and the inductive step is adding edges between two of these $n$ vertices.

From any proper $2$-colouring of a graph, you can obtain another by toggling the colours in any connected component.

To be able to add an edge $ij$ an obtain a forest, the vertices $i$ and $j$ must have already been in distinct connected component (otherwise the introduction of $ij$ adds a cycle). So, if it turns out that $i$ and $j$ have the same colour, we toggle the colours of the connected component containing $j$, then add the edge $ij$.

$\endgroup$
  • $\begingroup$ I think the point I was missing was that you could just switch the colour of every node in a component and it would remain valid. So this answers the question, but I think the induction on edges alone is nicer. Thanks for the answer though! $\endgroup$ – Callum M Apr 9 '13 at 15:58

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.