Fue descubierto independientemente, también en 1931, por Jenő Egerváry en el caso más general de grafos con peso.[4] Para grafos que no son bipartitos, el máximo emparejamiento y el problema de cubrimiento de vértices mínimo son muy diferentes en complejidad: el emparejamiento máximo puede ser encontrado en tiempo polinómico para cualquier grafo, mientras el cubrimiento de vértices mínimo es NP-completo.El complemento de un cubrimiento de vértices en cualquier grafo es un conjunto independiente, así que un cubrimiento de vértices mínimo es complementario a un conjunto independiente máximo; encontrando los conjuntos independientes máximos es otro problema NP-completo.Dado que emparejamiento bipartito es un caso especial de flujo máximo, el teorema también es resultado del teorema del corte mínimo.[6] El teorema de König está nombrado después del matemático húngaro Dénes Kőnig.Kőnig Había anunciado en 1914 y publicado en 1916 los resultados que cada grafo bipartito regular tiene un emparejamiento perfecto, y más generalmente que el número cromático de cualquier grafo bipartito es igual a su grado máximo[6] @– la última declaración es conocida comoTeorema de Coloración de la Línea de König .[7][8] Aun así,Bondy y Murty (1976) & Murty (1976) se atribuyó el teorema de König en un papel más tardío de Kőnig (1931).Según Biggs, Lloyd & Wilson (1976), Kőnig atribuyó la idea de estudiar emparejamientos en grafos bipartitos a su padre, matemático Gyula Kőnig.En húngaro, Kőnig el nombre tiene un acento agudo doble, pero su teorema es normalmente deletreado en caracteres alemanes.De modo parecido, no puede haber ningún emparejamiento más grande , porque cualquier arista emparejada tiene que incluir al menos un final en el cubrimiento de vértices, así que esto es un emparejamiento máximo.El teorema de König declara que la igualdad entre las medidas del emparejamiento y el cubrimiento (en este ejemplo, ambos números son seis) aplica más generalmente a cualquier grafo bipartito.el conjunto de vértices que está eno pertenece a un camino alterno (y tiene un final derecho enAun así, ninguna arista emparejada puede tener ambos de su finales en ., y tiene que ser un cubrimiento de vértices mínimo.[10] La construcción descrita en la prueba encima proporciona un algoritmo para producir un cubrimiento de vértices mínimo dada un emparejamiento máximo .Así, el algoritmo Hopcroft@–Karp para encontrar emparejamientos máximos en grafos bipartitos también puede solucionar el problema de cubrimiento del vértices eficientemente en estos grafos.Emparejamiento Bipartito Máximo puede ser aproximado arbitrariamente con exactitud en tiempo constante por algoritmos distribuidos; en contraste, aproximando el cubrimiento de vértices mínimo de un grafo bipartito requiere al menos tiempo logarítmico.
Un ejemplo de un grafo bipartito, con un máximo emparejamiento (azul) y cubrimiento mínimo (rojo) ambos de tamaño seis.
