5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This problem is nice. $\endgroup$
    – Arpan1729
    Oct 4, 2017 at 9:05

1 Answer 1

4
$\begingroup$

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).

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .