Partycja wierzchołków grafu

[tkrass]

Udowodnić, że wierzchołki każdego grafu G można podzielić na dwa podzbiory \(\displaystyle{ V_1}\) i \(\displaystyle{ V_2}\) w ten sposób, że każdy ze związanych z nimi podgrafów ma nie więcej niż \(\displaystyle{ \frac{e(G)}{3}}\) krawędzi.