Grafy spójne

Grzech903 · Post autor: **Grzech903** » 8 lut 2017, o 13:46

mam takie zadanie i szczerze nie wiem jak je ugryźć:(

Ze zbioru niespójnych grafów o n wierzchołkach wybierzmy taki graf G, który ma
najwieksza liczbe krawedzi. Pokazac, ze G ma dokładnie dwie składowe spójne.

Dzięki za każdą pomoc!

yorgin · Post autor: **yorgin** » 8 lut 2017, o 13:55

Idea:

Gdyby graf miał \(\displaystyle{ N>2}\) składowe, to można dorysować \(\displaystyle{ N-2}\) krawędzie, wszystkie wychodzące z jednego wierzchołka jednej składowej i łączące dowolny wierzchołek w każdej z \(\displaystyle{ N-2}\) pozostałych składowych. Tak otrzymany graf nadal jest niespójny, ale ma więcej krawędzi niż wyjściowy.

Grzech903 · Post autor: **Grzech903** » 8 lut 2017, o 15:15

Dzięki pomogło to może za ciosem zadam kolejne pytanie . Mam takie zadanie:

Niech G bedzie grafem majacym 5 wierzchołków , z których jeden ma stopien 2. Pokazac,
ze G jest planarny.

Czy dobrze mysilę ze skoro K5 to jest on nie planarny z twierdzenia Kuratowskiego?

yorgin · Post autor: **yorgin** » 9 lut 2017, o 07:16

Raczej nie jest on \(\displaystyle{ K_5}\). Poza tym piszesz, że nie jest planarny, a masz przecież pokazać, że jest...

Skoro jest wierzchołek stopnia \(\displaystyle{ 2}\), graf jest różny od \(\displaystyle{ K_5}\), więc jest planarny, na mocy tw. Kuratowskiego.