I have a question in combinatorics/graph theory about edge coloring that I ran into in some test in combinatorics and that I couldn't solve. The question goes like this:

Let $G$ be an undirected graph with $n$ vertices and let $d\ge2$. We give each edge in this graph some color from a set with $k$ colors (where $k\ge n$). Every color is in at most $d$ edges and every vertex touches at least $2d$ colors (that also means $\deg(v)\ge2d$).

Prove that there is some subgraph $G'$ (with the same vertices as $G$), so that every edge has a unique color (no color appears twice) and for every $v\in V(G)$ the degree is $\deg_{G'}(v)\ge1$ (so every vertex is connected to at least one edge).

I tried to think of some way to use the pigeonhole principle but I do not know what may be the "pigeons". I would be glad for some direction for the proof.

  • $\begingroup$ This problem is nice. $\endgroup$ – Arpan1729 Oct 4 '17 at 9:05

I would map the problem to Hall's Marriage Problem!!!

Let the set $V$ denote the set of all vertices of the graph $G$

$V=\{v_1,v_2, \dots ,v_n\}$

Let $C$ denote the set of all colours present.

$C=\{c_1,c_2, \dots,c_k\}$

Let $H$ be a bipartite graph with input set $V$ and output set $C$, and $v_i$ is connected to $c_j$ if and only if $v_i$ has an edge which is coloured with the colour $c_j$ in the graph $G$. So this defines a matching from $V$ to $C$. Now think for a moment that the given problem is solved if we find a perfect matching from $V$ to $C$.

If we find a perfect matching we can easily construct such a subgraph, we will take a vertex $v$ of $G$ then among the edges it is connected to, we will pick any one edge of the colour, $v$ is mapped to in the perfect matching. We would do this for all the vertices. This would form a subgraph with every edge having a unique colour and every vertex with degree at least $1$.

Now take any subset of $X$ of $V$ , Let $Y$ denote the set of colours which are connected to some vertex from the set $X$ in $H$($H$ is the matching defined above).

In order to prove the existence of perfect matching we just need to show $|Y|\geq |X|$.

Now each vertex in $X$ has at least $2d$ edges attached to it, and each edge can be attached to at most $2$ vertices, hence there are at least $2d|X|/2$ many distinct edges which are connected to some point of $X$ in the graph $G$. Now each colour is associated to atmost $d$ edges, hence there must be at least |X| colours which are connected to some point of $X$ in the graph $H$.

Hence $|Y|\geq |X|$, thus satisfying hall condition for perfect matching, hence our problem is solved.

(Note that we have sometimes viewed the set $C$ as some vertices of $H$, and sometimes as just colours of edges of $G$, and similarly we have treated the set $V$, sometimes as vertices of $G$, and sometimes as vertices of $H$, but I hope things are pretty clear).


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.