Emparejamiento bipartito con dominación de grado

Dado un gráfico bipartito no ponderado . ¿Es cierto que siempre existe una coincidencia no vacío M ⊆ E (no necesariamente máxima), tal que para cada ( i , j ) ∈ E con i emparejado y j inigualable, que posee grados ( i ) > deg ( j ) ? Aquí ( i , j ) ¿no ordenado, es decir, i puedo ser de cualquier lado.$G=(V, E)$$M\subseteq E$$(i,j)\in E$$i$$j$$\deg(i)>\deg(j)$$(i,j)$$i$

Mi intuición sobre por qué esto es cierto es que, cuando cada vértice en tiene el mismo grado, siempre hay una coincidencia perfecta, que es la coincidencia que requerimos. Para algunas estructuras gráficas simples, como árboles o gráficos unicíclicos, se desea una coincidencia máxima ya que el grado de una hoja siempre es menor que su padre.$V$

Traté de demostrarlo a partir del teorema de Hall, pero fallé. Parte de la complejidad de este problema es que la solución no siempre es una coincidencia máxima. Por ejemplo, considerando un gráfico que consiste en dos 4 ciclos y d e f g . Entonces M = { a b , c d } y sus coincidencias simétricas son las únicas soluciones, que no son máximas.$abcd$$defg$$M=\{ab,cd\}$

No siempre existe una coincidencia con su propiedad en un gráfico bipartito.

$G = (V, E)$

• $V = \{a_1, a_2, a_3, b_1, b_2, b_3, c_1, c_2, d_1, d_2, x\}$
• $E = \{a_1, a_2\} \times \{c_1, c_2, x\} \cup \{b_1, b_2\} \times \{d_1, d_2, x\} \cup \{(a_3, c_1), (a_3, d_2), (a_3, x), (b_3, d_1), (b_3, c_2), (b_3, x)\}$

$V_1 = \{a_1, a_2, a_3, b_1, b_2, b_3\}$$V_2 = \{c_1, c_2, d_1, d_2, x\}$$x$$3$$x$$6$

$M$$v_1$$v_2$$M$$M$$v_1$$M$$deg(v_1) > deg(v_2)$

$G$$V \setminus \{x\}$$3$$V \setminus\{x\}$$M$$M$$V_1$$M$$V_1$$V_2$$G$$M$$x$$M$

$M$$G$