graf spojny Krystek: Czy każdy graf regularny stopnia 6 o 13 wierzchołkach jest spójny wiec |E|=13*6/2=39 na podstwie tw.ze Każdy graf spójny o n wierzchołkach ma co najmniej n − 1 krawędzi. mozna stwierdzic ze graf nie jest spojny moze byc?

Krystek: tzn.bedzie grafem spojnym bo ma co najmniej n−1 krawedzi?

Blee: Graf spojny => ma conajmniej n−1 krawedzi To mowi twierdzenie. W druga strone to nie dziala. Nie kazdy graf o n−1 krawedziach przy n wierzcholkach bedzie spojny ( wiekszosc z nich nie bedzie)

Krystek: ok,rozumiem,to w jaki inny sposob mozna to wykazac?

Blee: Jakby wierzcholek jest stopnia 6 a graf jest regularny. Wybieramy dwa wiwrzcholki ktore NIE SA polaczone ze soba. Kazdy z nich laczy sie z 6 wierzcholkami. Wykaz, ze minimum jeden z wierzcholkow musi byc polaczony z obydwoma tymi wierzcholkami (spojny) lub ze zaden z nich nie bedzie polaczony z obydwoma tymi wierzcholkami (niespojny).

Krystek: to moze ktos ma pomysl jak to wykazac bo mi nic nie przychodzi ?

Pytający: Oznaczmy: V // zbiór wszystkich wierzchołków u∊V, v∊V, u≠v // 2 dowolne niesąsiadujące (niepołączone krawędzią) wierzchołki S_u⊂V // zbiór wierzchołków sąsiadujących z u S_v⊂V // zbiór wierzchołków sąsiadujących z v I wtedy: W=V\{u,v} |W|=13−2=11 |S_u|=|S_v|=6 |W|≥|S_u∪S_v|=|S_u|+|S_v|−|S_u∩S_v| |S_u∩S_v|≥|S_u|+|S_v|−|W|=6+6−11=1, więc istnieje droga z u do v (bo przynajmniej 1 wierzchołek sąsiaduje jednocześnie z u i z v), zatem graf jest spójny.

Krystek: ok,dzięki wielkie