Tamanho da correspondência máxima no gráfico bipartido

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

Dado um gráfico bipartido e um máximo de M correspondente de G , através do Teorema de Konig , vemos que | M | = | C | onde C é uma cobertura mínima de vértices para $G = (U,V,E)$$M$$G$$|M| = |C|$$C$$G$ . Sua declaração é apenas um limite superior do tamanho da correspondência possível, não uma igualdade estrita.

A imagem na página da Wikipedia fornece um bom contra-exemplo para sua reivindicação. Nós vemos isso , enquanto min ( | U | , | V | ) = 7 .$|M| = 6$$\min(|U|,|V|) = 7$

No entanto, no caso de um gráfico bipartido completo sua declaração é válida.$K_{n,m}$

Não. Por exemplo, considere o caso em que os dois lados estão desconectados $|E| = 0$ ou o caso em que um grande grupo de nós está conectado ao mesmo nó único:

$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$