Graphhomomorphismus/In bipartiten Graphen/Aufgabe/Lösung


Es sei eine bipartite Zerlegung von . Dann ist eine Zerlegung. Diese ist auch bipartit. Würde es nämlich in eine Kante mit

geben, so würde es direkt auch die Kante innerhalb von in geben, ein Widerspruch.