Prove that a bipartite graph has a unique bipartition if and only if it is connected Prove that a bipartite graph has a unique bipartition if and only if it is connected. 
I am completely stuck on this question. I assume it is a proof that involves a mixing of definitions but I am not sure. 
 A: If the graph is connected and bipartite it has a unique bipartition, to see this take a spanning tree, pick a root vertex. Then the parity of the distance from each vertex to the root will define the two sets.
If the graph is not connected and is bipartite each component must be bipartite, therefore you can find a bipartition for each component. So suppose the components are $C_1,C_2\dots C_n$ and each component has parts $A_1,A_2\dots A_n$ and $B_1,B_2\dots B_n$. Then you can take any set of the form $D_1,D_2,\dots D_n$ where $D_i$ is ethier $B_i$ or $C_i$ will give you a bipartition.
A: First suppose that G is a disconnected bipartite graph with bipartition (A, B).
Let G' be a component of G, set X = V (G') and let G'' = G − X. Setting A' = A ∩ X
and B' = B ∩ X we find that (A', B') is a bipartition of G' and similarly A'' = A \ X and
B'' = B \ X is a bipartition of G''. Now, since there are no edges between X and the rest of the graph it follows that (A, B) = (A' ∪ A'', B' ∪ B'') and (A' ∪ B'', B' ∪ A'') are inequivalent bipartitions of G.
Next suppose that (A, B) and (A', B') are bipartitions of G,with A' ≠ A and A0 ≠ B.
Set X = (A ∩ A') ∪ (B ∩ B') and Y = (A ∩ B') ∪ (A' ∩ B). It follows immediately that
X, Y are disjoint. If X = ∅ then A ∩ A' = ∅ and B ∩ B' = ∅ so A ⊆ B' and B' ⊆ A. But
then we have A = B' and B = A' giving us a contradiction. Thus X ≠ ∅ and by a similar
argument Y ≠ ∅. It follows from the existence of our bipartitions that any edge with an end in A ∩ A' must have its other end in B ∩ B' and similarly any edge with an end in B ∩ B' must have its other end in A ∩ A'. But then there are no edges from X to Y and therefore G is disconnected.
A: let's assume that the graph is connected.let's say that the graph is partitioned into two sets of vertices x and y such that every edge lies between one vertex of x and one vertex from y. I will try to prove by contradiction.So let's assume that there are two different bipartite partitions 'p1' and 'p2' of a graph.then we have at least one pair of vertices (a,b) such that in p1 they are in different sets(one in x and one in y),and in p2 they are in the same set(both of them in either x or y). Here we have two cases  
case(1): There is an edge between a and b .then p2 is not a bipartite partition since a and b are in the same set and they have an edge between them.hence the bipartite partition is unique.
case(2): there is no edge between 'a' and b.here we try to obtain p2 from p1 by simply shifting the vertices from x to y.let's say that b was in set y and a was in x in the partition p1. First of all, 'a' was shifted from x to y.then all the vertices in y which are adjacent to 'a' must be moved to x.This way we keep moving the vertices,since the graph is connected b must have had an edge with some vertex 'v' in x in p1.But as we move the vertices we must have moved 'v' from x to y.Now v and b both lie in set y.so b must be moved to x.that is every such vertex as b is moved ,during this transition ,which implies that the partition p2 is same as p1.  
