Udowodnij, że krawędzie dowolnego grafu nieskierowanego

[matinf]

Witam,
Udowodnij, że krawędzie dowolnego grafu nieskierowanego można skierować w taki sposób, że dla każdego wierzchołka \(\displaystyle{ v}\) spełniony będzie warunek:

\(\displaystyle{ |\deg_{in}(v) -\deg_{out}(v)}|\le 1}\)

Może ktoś podać wskazówkę ? Pod spojlerem może być nawet "mocniejsza" wskazówka.

[Hydra147]

Ukryta treść:    

Wykaż najpierw, że wystarczy rozważać grafy spójne.

Ukryta treść:    

Potem wykaż, że wystarczy rozważać drzewa (co można zrobić w grafie, w którym jest cykl?).

Ukryta treść:    

Potem zauważ, że wystarczy rozważać drzewa, w których nie ma wierzchołka stopnia \(\displaystyle{ 2}\) (jeśli jest to można go "przeskoczyć").

Ukryta treść:    

Na końcu zauważ, że krawędzie grafu wychodzące z wierzchołków o stopniu \(\displaystyle{ 1}\) można tak zorientować, że nie nie naruszą warunków zadania.

Łącząc te redukcje po kolei otrzymasz w końcu graf o \(\displaystyle{ 1}\) wierzchołku, dla którego teza jest oczywista.