Graphhomomorphismus/In bipartiten Graphen/Aufgabe/Lösung

Es sei ${}H=A\uplus B$ eine bipartite Zerlegung von ${}H$ . Dann ist ${}G=\varphi ^{-1}(A)\uplus \varphi ^{-1}(B)$ eine Zerlegung. Diese ist auch bipartit. Würde es nämlich in ${}G$ eine Kante ${}\{x,y\}$ mit ${}x,y\in \varphi ^{-1}(A)$

geben, so würde es direkt auch die Kante

{}\{\varphi (x),\varphi (y)\}

innerhalb von

{}A

in

{}H

geben, ein Widerspruch.

Zur gelösten Aufgabe

This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.