Graf 8 wierzchołków i 2 składowe spójne

[zielony789]

stopnie wierzchołków wynoszą: \(\displaystyle{ 1,1,2,1,1,1,2,1}\) uzasadnij że taki graf istnieje lub nie.

z rysunku wynika ze nie istnieje ale jak to uzasadnić teorią matematyczną?

[dabros]

załóżmy, ze nasz graf da się podzielić na dwie spójne składowe - ze względu na symetrię stopni wierzchołków będą to składowe identycznościowe. A więc w każdej składowej znajdzie się jeden wierzchołek stopnia \(\displaystyle{ 2}\) i trzy stopnia \(\displaystyle{ 1}\);w każdej takiej grupie możliwa jest konstrukcja jedynie drzewa z jednym korzeniem (wierzchołek o najwyższym stopniu, który jest połączony z pozostałymi), którego stopień jest równy sumie stopni pozostałych wierzchołków; ale \(\displaystyle{ 2<1+1+1}\), a więc sprzeczniość

[Qń]

załóżmy, ze nasz graf da się podzielić na dwie spójne składowe - ze względu na symetrię stopni wierzchołków będą to składowe identycznościowe.

Lemat nieprawdziwy - na przykład dla stopni: \(\displaystyle{ 1,1,1,1,2,2}\) graf można podzielić na dwie nieidentyczne spójne składowe.

Pozdrawiam.
Qń.

[dabros]

ale twoj przyklad na idntycznosciowe tez sie da;
chodzi o to, ze jezeli mozna graf podzielic na niesymetryczne skladowe, to tym bardziej da sie na symetryczne
tak jest zawsze - dlatego moj lemat nie jest falszywy
(o takie spostrzezenie mi chodzilo)

[Qń]

W takim razie udowodniłeś jedynie, że danego grafu nie da się podzielić na dwie identyczne składowe spójne, a chodziło o to by udowodnić, że nie da podzielić się na jakiekolwiek.

A, żeby nie było, że tylko czepiam się złych rozwiązań, to podam dobre:
Jeśli w tym grafie wierzchołki o stopniu 2 są połączone, to graf musi wyglądać tak:
\(\displaystyle{ 1-2-2-1, 1-1, 1-1}\)
(mam nadzieję, że wiadomo co znaczy taki nieformalny zapis),
a jeśli nie są połączone, to tak:
\(\displaystyle{ 1-2-1, 1-2-1, 1-1}\).
Ewentualnie, jeśli dopuszczamy, że dwa wierzchołki mogą być połączone dwiema krawędziami, to mamy:
\(\displaystyle{ 2=2, 1-1, 1-1, 1-1}\).

W każdym wypadku są przynajmniej 3 spójne składowe

Pozdrawiam.
Qń.

[dabros]

twoje rozwiazanie jest dobre, ale nie mozesz powiedziec ze moje jest zle - nie jest moze tak oczywiste jak twoje ale dziala rowniez w ogolnym przypadku (gdy mamy wierzcholki stopnia 1)

[Qń]

Twoje rozwiązanie jest złe.
Albo mówisz: jeśli się da podzielić, to składowe muszą być identyczne - i wtedy sprzeczność. Ale to błąd, bo wcale nie muszą.
Albo też mówisz: może istnieć podział na 2 składowe identyczne, ale gdyby istniał to mamy sprzeczność. To z kolei dowodzi tylko nieistnienia podziału na 2 składowe identyczne, a nie na dwie dowolne.

Pozdrawiam.
Qń.