Podział zbioru punktów na dwa zbiory

[6234945]

Mam taki problem nad którym się dość długo już głowię i nie mam żadnego pomysłu.
"Dane jest \(\displaystyle{ n}\) punktów. Każdy punkt jest połączony z innymi punktami odcinkiem. Punkty nazwiemy sąsiadami jeśli łączy je odcinek (jeśli punkt \(\displaystyle{ A}\) jest połączony z punktem \(\displaystyle{ B}\) to zarówno \(\displaystyle{ A}\) jest sąsiadem \(\displaystyle{ B}\) jak i \(\displaystyle{ B}\) jest sąsiadem \(\displaystyle{ A}\)). Każdy punkt ma nie więcej niż 3 sąsiadów. Wykazać że możemy podzielić punkty na dwie rozłączne grupy aby każdy punkt w swojej grupie miał maksymalnie jednego sąsiada"
I to właściwie wszystko. Jeśli coś za bardzo przekombinowałem to mogę jeszcze raz wyjaśnić treść.

[arek1357]

W moim odczuciu możesz potraktować ten układ jako graf o stopniach wierzchołków nie większych od trzech, podzielić go na składowe spójne i w każdą składową dzielić na drogi lub cykle jak największe, np:

\(\displaystyle{ A-B-C-D-E-F-G...}\)

Potem wybierać i wrzucać do pierwszego zbioru:

\(\displaystyle{ A-B, D-E, G-H,...}\)

A to co zostanie wrzucamy do drugiego zbioru, i tak postąpić z każdą składową...

W sumie te utworzona zbiorki to grafy o stopniach wierzchołków nie więcej nić jeden...

Właściwie to taka konstrukcja a nie formalny dowód...

[6234945]

A co jeśli cały graf jet spójny i podział nie jest możliwy?

[arek1357]

Jeżeli cały graf jest spójny tym łatwiej, np:

Spójny masz a nawet cykliczny:

\(\displaystyle{ A-B-C-D-E-F-A}\)

Wybierasz:

Pierwszy zbiór:

\(\displaystyle{ A-B, D-E}\)

Drugi zbiór:

\(\displaystyle{ C, F}\)

Chodziło mi o to, że każdą składową spójną tak samo traktujesz...