Tamaño de coincidencia máxima en gráfico bipartito

$M$$G(U, V, E)$$\min(|U|, |V|)$

Dado un gráfico bipartito y una coincidencia máxima de , a través del teorema de Konig vemos quedonde es una cubierta de vértice mínimo para . Su declaración es simplemente un límite superior en el tamaño de la posible coincidencia, no una igualdad estricta.$G = (U,V,E)$$M$$G$$|M| = |C|$$C$$G$

La imagen en la página de wikipedia proporciona un buen contraejemplo a su reclamo. Vemos que , mientras que .$|M| = 6$$\min(|U|,|V|) = 7$

Sin embargo, en el caso de un gráfico bipartito completo su declaración se mantiene.$K_{n,m}$

No. Por ejemplo, considere el caso donde los dos lados están desconectados o el caso donde un gran grupo de nodos están todos conectados al mismo nodo único:$|E| = 0$

$U = u_1, u_2, ..., u_n$

$V = v_1, v_2, ... , v_n$

$E = u_1v_1, u_2v_1, ... u_nv_1,$ $v_1u_1, v_2u_1, ... v_nu_1$