[Teoria grafów] dowód, graf dwudzielny, graf planarny

[matinf]

Witam,

Mamy graf planarny, taki że każdy region jest ograniczony cyklem parzystej długości. Pokazać, że graf jest dwudzielny.

Wystarczy więc, jeśli pokażę że każdy cykl ma parzystą długość- równoważnie mamy dwudzielność.

I moja propozycja jest taka:

Rozważmy dowolny cykl. Wewnątrz tego cyklu powstaje jakiś region. No siłą rzeczy, nie ma innej możliwości. A skoro powstaje region, to zgodnie z założeniem cykl jest parzystej długości. Czyli wszystkie cykle są parzystej długości.


To jest prawidłowe rozumowanie ?

[bartek118]

Nie do końca. A co jeśli w środku tego cyklu powstaną dwa, trzy, lub większa liczba regionów?

[matinf]

Nie do końca. A co jeśli w środku tego cyklu powstaną dwa, trzy, lub większa liczba regionów?

To jest oczywiście prawda.

To załóżmy, że zaszła sytuacja, o której mówisz (w przeciwnym razie moje rozumowanie).

Wówczas oznaczmy przez \(\displaystyle{ T}\) cykl, w którym siedzą mniejsze cykle: \(\displaystyle{ t_1, t_2,...,t_n}\)
Tzn, jest \(\displaystyle{ n}\) regionów wewnątrz dużego cyklu \(\displaystyle{ T}\) , którego parzystości oczekujemy.

Dla każdego regionu policzmy krawędzie. Tzn piszemy tak:
\(\displaystyle{ 1 + 1+ 1 +1 + 1 +....}\). Czyli będziemy przeglądać dla każdego regionu jego krawędzie i dopisywać jedynkę do sumy.
Jest jasne, że niektóre krawędzie policzymy dwukrotnie, ale właśnie o to chodzi. Jest również jasne, że krawędzie cyklu \(\displaystyle{ T}\) policzymy jednokrotnie.
Oczywiście otrzymana suma z jedynek musi być parzysta, bo tak mówi założenie zadania. Teraz Od tej liczby odejmiemy parzystą liczbę, tzn sumę wszystkich krawędzi regionów, ale wewnętrznych. Pozostała liczba parzysta, ale ta liczba to liczba krawędzi na cyklu \(\displaystyle{ T}\)

Ok ?

[bartek118]

Tak, wygląda OK