Borde para colorear - subconjunto con exactamente una vez cada color

Question

Tengo una pregunta en la combinatoria/teoría de grafos sobre el borde de una coloración que me encontré en alguna prueba en la combinatoria y que yo no podía resolver. La pregunta dice así:

Deje $G$ ser un grafo no dirigido con $n$ vértices y deje $d\ge2$. Damos a cada uno de ventaja en este gráfico un poco de color a partir de un conjunto con $k$ colores (donde $k\ge n$). Cada color es en la mayoría de los $d$ bordes y cada vértice toca, al menos, $2d$ colores (que también significa $\deg(v)\ge2d$).

Demostrar que hay algunos subgrafo $G'$ (con los mismos vértices $G$), de forma que cada arista tiene un único color (color no aparece dos veces) y para cada $v\in V(G)$ el grado es $\deg_{G'}(v)\ge1$ (para cada vértice está conectado a al menos uno de los bordes).

Traté de pensar en alguna manera de usar el principio del palomar, pero no sé lo que puede ser el "palomas". Yo estaría encantado de alguna dirección para la prueba.

Answer 1

Me gustaría mapa el problema a la Sala del Matrimonio Problema!!!

Deje que el conjunto de $V$ denota el conjunto de todos los vértices del grafo $G$

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

Deje $C$ denota el conjunto de todos los colores presentes.

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

Deje $H$ ser un bipartito grafo con conjunto de entrada $V$ y el conjunto de salida $C$, e $v_i$ está conectado a $c_j$ si y sólo si $v_i$ tiene un borde de color con el color de la $c_j$ en el gráfico de $G$. Así que de esta forma se define una correspondencia de$V$$C$. Ahora piense por un momento en que el problema se resuelve si nos encontramos con un perfecto maridaje de$V$$C$.

Si encontramos un perfecto maridaje podemos construir fácilmente un subgrafo, vamos a tomar un vértice $v$$G$, entre los bordes está conectado, vamos a recoger a cualquier uno de los bordes del color, $v$ es asignado en el perfecto maridaje. Nos gustaría hacer esto para todos los vértices. Esto constituiría un subgrafo con cada borde de tener un color único y cada vértice con grado de al menos $1$.

Ahora tomar cualquier subconjunto de a$X$$V$ , Vamos a $Y$ denotar el conjunto de colores que están conectadas a algún vértice del conjunto $X$ en $H$($H$ es la coincidencia de la definición anterior).

Con el fin de demostrar la existencia de la perfecta coincidencia sólo tenemos que mostrar $|Y|\geq |X|$.

Ahora cada vértice en $X$ tiene al menos $2d$ bordes conectados a él, y cada borde puede ser conectado en la mayoría de las $2$ vértices, por lo tanto, hay por lo menos $2d|X|/2$ muchas distintos a los bordes, que están conectadas a algún punto de $X$ en el gráfico de $G$. Ahora cada color está asociado a atmost $d$ bordes, por lo tanto, no debe ser al menos de |X| colores que están conectados a un punto de $X$ en el gráfico de $H$.

Por lo tanto $|Y|\geq |X|$, cumpliéndose así el hall condición para una perfecta coincidencia, por lo tanto, nuestro problema está resuelto.

(Tenga en cuenta que a veces hemos visto que el conjunto de $C$ como algunos vértices de $H$, y a veces sólo como los colores de los bordes de las $G$, y del mismo modo hemos tratado el conjunto $V$, a veces como vértices de $G$, y a veces como vértices de $H$, pero espero que las cosas son bastante claras).