# A non-proper edge-coloring of a bipartite graph

This is an exercise from Graph Theory with Applications by Bondy and Murty:

6.1.6 Show that if $G$ is bipartite with $\delta>0$, then $G$ has a $\delta$-edge coloring such that all $\delta$ colors are represented at each vertex.

Induction on $\delta$ is no good.

I tried using that since $G$ is bipartite, $\chi'(G)=\Delta(G)$. So there exists a proper $\Delta$-edge coloring $\mathcal C=(E_1,E_2,\dots,E_\delta,\dots,E_\Delta).$ We would then need to recolor all the edges that have color $E_i$, for any $i>\delta$, to a color $E_j$ where $j\leq\delta$ such that each vertex sees every color $E_1, E_2, \dots,E_\delta$. I cannot see a way to do this, however.

EDIT

A generalized result is located here. It uses induction on the number of edges, which seems promising. Basically, we take a vertex $u$ that has maximum degree, and remove any edge $uv$. Then $H=G\backslash\{uv\}$ has a $\delta(H)$ coloring that we want. So, if $\delta(H)=\delta(G)$, we are done. But if $\delta(H)=\delta(G)-1$, well, I'm stuck here.

• Why do you say induction on $\delta$ is no good? – Mathily Nov 1 '16 at 15:53
• If $\delta=1$, we color all edges with color 1. So, for example, lets say $\delta=2$ then remove an edge from a vertex with degree $2$. Now we have a graph with $\delta=1$, and so we can color every edge with color 1. Adding back that edge, we can color it with color $2$. But what of all the other edges? – Bonnaduck Nov 1 '16 at 15:56
• Instead of removing one edge from one vertex, remove a perfect matching. – Mathily Nov 1 '16 at 16:00
• @Mathily There could be no perfect matching, but removing some (e.g., maximal) matching could work. – dtldarek Nov 2 '16 at 9:10
• @dtldarek good point. There is a lot more subtlety to this than I was thinking . Even a maximal matching doesn't clearly allow induction as you might not decrease $\delta$. – Mathily Nov 2 '16 at 13:55

Disclaimer:

I think the argument in the paper by M. Iradmusa, S. Akbari and M. Jammali you linked is great, especially the strenghtening of the thesis is what allowed them to arrive at such a concise proof. In fact, I think strenthening of the hypothesis is the right thing to do, because when doing induction you would like other vertices taken care of, even if the one you are considering currently has a strictly smaller degree (and the orginaly claim does not allow that). Just take the generalized version, and then infer the weaker as a corollary by setting $t = \delta$.

Still, if you do not want to go that way, here is another proof which goes color-by-color, that is, I construct a subset of edges, such that it touches all the vertices, and reduces the minimum degree at most by one. I do not give all the details (in particular base of the induction, and all the "glue" necessary in a formal proof), but I think it will be enough for you to complete it on your own.

Proof (induction step):

A nice starting point is a maximum matching, but then it does not need to touch all the vertices. Obviously, what we need to do is to use non-minimal-degree vertices more than once. Thus, we create a new temporary graph $G'$ in which

• we first remove any edge between two vertices of degree strictly larger that $\delta$;
• for each vertex $v \in V$ we insert $\deg(v) - \delta$ additional copies of $v$, so that each vertex has $(\deg(v) - \delta + 1)$ copies of itself.

The following diagram illustrates the construction. Removed edges were marked by a dashed line, while additional copies of vertices were colored red. Observe that there are no red-red edges, only black-black and red-black (the example should be bipartite, it isn't, because the picture would be too big, sorry).

Suppose that $M \subseteq E'$ is a maximum matching in $G'$ and that $N \subseteq E$ is its flattened version. Obviously removing $N$ cannot decrease any degree below $\delta-1$, but we do need to prove that there exists a matching that touches at least each vertex (not a copy) once. In other words, we would like to prove that it saturates all the black vertices. Normally we could use the Hall's theorem to show it, but black vertices belong to both partitions. Thus, we will use an extended version of Hall's theorem:

A bipartite graph $G$ contains a matching $M$ that matches all vertices of $X \subseteq V$ if and only if it satisfies $$\forall Y \subseteq X.\ |Y| \leq |\mathcal{N}(Y)|. \tag{\spadesuit}$$

Note that $X$ is just any subset of $V$ (that is, all vertices of $G$), not necessarily a subset of just one partition. This version can be obtain from the standard version of Hall's theorem by considering $X \cap V_1$ and $X \cap V_2$ (i.e., splitting $X$ according to the bipartition of the graph) and then merging the respective matchings. For a less direct, but a really nice fix-point proof see here.

To prove that $(\spadesuit)$ holds in $G'$, we will split $Y = Y_1 \uplus Y_2$ where $Y_i = Y \cap V_i$ and observe that, because the graph is bipartite and the respective sets are disjoint, that is, $Y_1 \cap Y_2 = \varnothing$ and $\mathcal{N}(Y_1) \cap \mathcal{N}(Y_2) = \varnothing$, it is enough to prove $|Y_i| \leq |\mathcal{N}(Y_i)|$ separately for each $i \in \{1,2\}$.

Fix $i$ and consider graph $H = G'[Y_i\cup\mathcal{N}(Y_i)]$. The crucial thing to observe is that, due to vertices of $Y_i$ being all black, vertices from $\mathcal{N}_{G'}(Y_i) = \mathcal{N}_G(Y_i)$ have no red neighbors in $H$, and consequently no red-black edges. Thus, for any vertex $v \in Y_i$ and any neighbor $u \in \mathcal{N}(v)$:

• $\operatorname{blackdeg}_H(v) > \delta$ implies $\operatorname{blackdeg}_H(u) = \deg_H(u) = \delta$;
• $\operatorname{blackdeg}_H(v) = \delta$ implies $\operatorname{reddeg}_H(u) \geq \deg_{G'}(u)-\delta = \deg_H(u)-\delta$.

Consequently, $\deg_H(v) \geq \deg_H(u)$ for any $v \in Y_i$ and $u \in \mathcal{N}(v)$, and $|Y_i| \leq |\mathcal{N}(Y_i)|$, which is what we wanted to prove.

Once we get a black-saturating matching $M$ in $G'$, you can flatten it to obtain a subset of $E$ and paint all these edges with one color, while the rest can be taken care of by the inductive hypothesis.

I hope this helps $\ddot\smile$

• @Bonnaduck It took a while, but I made a mistake at first, and then had other matters to attend to. The proof should be alright now. – dtldarek Nov 10 '16 at 13:24
• I have no idea why, but I was never notified of this answer! Thank you! Very detailed! – Bonnaduck Nov 22 '16 at 18:54