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 for the graph returned by the algorithm Dsatur, that 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 ?

Note the following. If among all vertices $v$ with maximum $\mathrm{DSAT}(v)$ we will always take a vertex that was the first to reach this value, then for a case of connected bipartite graph Dsatur algorithm becomes usual breadth-first search. If we always take a vertex that was the last to reach maximum $\mathrm{DSAT}(v)$ then it becomes depth-first search.

Both searches can be used for bipartity check. And both searches build some spanning tree of given graph. Dsatur algorithm for in case of connected bipartite graph also implicitly builds a spanning tree even if at each step you choose arbitrate vertex with maximum $\mathrm{DSAT}(v)$.

Let induction hypothesis be the following: all colored vertices from the first part have the first color and all colored vertices from the second part have the second color. It evidently holds after coloring only one vertex.

So by induction hypothesis the next vertex $u$ chosen to be colored has all adjacent colored neighbours in the opposite part and all of them are colored in the same color. Also since the graph is connected if at least one vertex is not colored then there always exists a non-colored vertex adjacent to a colored vertex. This means that $\mathrm{DSAT}(u) \ge 1$. But induction hypothesis implies that $\mathrm{DSAT}(u) \le 1$. So $\mathrm{DSAT}(u) = 1$. This means that $u$ will be colored into appropriate color 1 or 2 according to its part and we proved that induction hypothesis holds for $k + 1$ vertices if it holds for $k$ vertices.

• Thank you for your answer ! induction hypothesis implies that $DSAT(u)≤1$ I have some difficulties to understand it from the hypothesis : all colored vertices from the first part have the first color and all colored vertices from the second part have the second color. Can you develop this idea please ? Commented Mar 16, 2017 at 22:00
• Why is it so evident for the first colored vertex ? Commented Mar 16, 2017 at 22:06
• Let induction hypothesis be the following: all colored vertices from the first part have the first color and all colored vertices from the second part have the second color. This means that for any vertex $v$ all vertices adjacent to $v$ are either non-colored or colored to the same color (the color of thier part), because graph is bipartite. After coloring the first vertex we have only one colored vertex this evidently implies that there are no two vertices of different colors in the same part, because there are no two colored vertices at all. Commented Mar 16, 2017 at 23:33

With reference to your picture, suppose an algorithm picked uncolored vertices at random and gave them the lowest color not used for their neighbors.

This algorithm may pick a vertex $v$ from $V$ and color it blue; then choose a vertex $u$ from $U$ not connected to $v$ and color it... blue again. If the bipartite graph is connected, that will lead to using more than two colors.

Your task is to show that the DSATUR algorithm will never do that. To that effect, note that whether the lowest color goes to vertices in $V$ or vertices in $U$ doesn't matter. We'll suppose it goes to $V$.

Once the first color is assigned, though, we always want next to pick a vertex that has already a colored neighbor. Since the graph is bipartite, we'll assign the "other" color to it and all will be well.

The connectedness of the graph guarantees that we can continue to do so until all vertices are colored.

The key observation, at this point, is that as long as there are both colored and uncolored vertices, the maximum DSAT of an uncolored vertex is greater than 0.

I hope you find this reasoning convincing, but it's not a formal proof yet. How to make it into one? We'll use induction. Specifically, let "blue" stand for $0$ and "green" for $1$. Suppose, without loss of generality, that a vertex in $V$ is initially colored blue.

We want to prove the following invariant: Whenever the algorithm asks whether there remain uncolored vertices, all colored vertices in $V$ are blue, and all colored vertices in $U$ are green.

This invariant is obviously true after initialization.

Now for the induction step. If there are no more uncolored vertices, the inductive hypothesis implies that all $V$ vertices are blue and all $U$ vertices are green. Success!

Suppose next that there still are uncolored vertices. There must be at least one edge connecting an uncolored vertex $u$ to some colored vertex, or else the graph wouldn't be connected. DSAT of this vertex $u$ must be positive. Hence the vertex that is picked by DSATUR has colored neighbors.

Suppose $u$ is in $U$ (the other case is symmetric). Then its colored neighbors (there may be more than one) are all in $V$ because the graph is bipartite. By the inductive hypothesis, they are all colored blue. Hence $u$ gets colored green, preserving the invariant. We are done.

• as long as there are both colored and uncolored vertices, the maximum $DSAT$ of an uncolored vertex is greater or equal than $0$, no ? Commented Mar 16, 2017 at 15:45
• No, the key point is that the maximum is strictly positive. This is true because the graph is connected, which means that there exists an uncolored vertex with colored neighbors. Commented Mar 16, 2017 at 15:48
• Yes, understood Commented Mar 16, 2017 at 15:49