How may an algorithm always color optimally connected bipartite graphs? Let's consider a greedy algorithm for the coloration problem called the Dsatur algorithm, designed by Daniel Brélaz in 1979 at the EPFL, Switzerland.. This algorithm is based on an order of vertices which we can obtain from considering the saturation degree of each vertex $v$ from $G$. The saturation  degree of a vertex $v$ , which we can write as $DSAT(v)$, is the number of color, the number of different colors used in $v$ neighborhood. The idea is to color  first the vertices with a saturation degree high enough to avoid using too many colors. 

Data : an undirected (*non-orienté*) connected graph $G=(V,E)$.
Output : all vertices of $G$ colored.

SORT the vertices by decreasing order of degrees.
COLOR a vertex of maximum degree with color 1.
While it exists vertices not colored do 
  CHOOSEa vertex $v$ with max DSAT
  COLOR $v$ with the smallest possible color
  UPDATE DSAT for all neighbors of v


How to show that DATSUR Algorithm always  color optimally connected bipartite graphs ?



My attempt

I think I have to prove it by the absurd :


As far as it is a conected graph it can't be colored by one color solely.
If there were three colors returned by the algorithm Dsatur, taht would mean that a vertex would return $Dsatur(v)= 2$ (it exists two neighbors with two different colors). Which is impossible. But why ?


That would mean that it gives three kind of different colors... But I don't know how to show why this is impossible... Can you help me ?
You can prove an even stronger claim. Consider the following algorithm:

Let $v_1,\ldots,v_n$ be an ordering of the vertices such that for $i&gt;1$, each $v_i$ is connected to at least one of $v_1,\ldots,v_{i-1}$.
Go over all vertices $v_1,\ldots,v_n$ in order, and color each one with the smallest available color.

This algorithm also uses (at most) two colors to color a connected bipartite graph. The property of the ordering that I highlight, which is satisfied by the ordering produced by the Dsatur algorithm, suffices to guarantee that the algorithm uses the minimal number of colors.
To prove that this algorithm works for a connected bipartite graph with bipartition $V_1 \cup V_2$, where $v_1 \in V_1$, prove by induction that if $v_i \in V_j$ then $v_i$ gets colored $j$.