Edge Coloring - subset with every color exactly once 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.
 A: 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).
