Grafy konpopoz: Zadanie 5. Przyjmując, że G jest grafem prostym o n wierzchołkach i m krawędziach wykaż

	n(n−1)
indukcyjnie, że m ≤		. Dla jakich grafów zachodzi równość?
	2

Zadanie 6. Rozważ wszystkie grafy o zbiorze wierzchołków V = {v₁, v₂, v₃} i wskaż te, które są izomorficzne.

I'm back: 5) rownosc zachodzi dla grafu pełnego. Potraktuj to jako wskazówkę do wykazania samej nierownosco

kerajs: 6) skoro ''wszystkie grafy'' to pewnie chodzi o grafy proste (czyli bez pętli, multikrawędzi i wierzchołków odizolowanych). Są tylko cztery takie grafy: a) deg(v₁)=2 , deg(v₂)=1 , deg(v₃)=1 b) deg(v₁)=1, deg(v₂)=2 , deg(v₃)=1 c) deg(v₁)=1 , deg(v₂)=1 , deg(v₃)=2 d) deg(v₁)=2 , deg(v₂)=2 , deg(v₃)=2 izomorficzne są a), b) i c)

kerajs: Jeśli wykładowca za grafy proste uznaje także grafy niespójne bez pętli i krawędzi wielokrotnych to możliwą są jeszcze: e) deg(v1)=0 , deg(v2)=0 , deg(v3)=0 f) deg(v1)=0, deg(v2)=1 , deg(v3)=1 g) deg(v1)=1 , deg(v2)=1 , deg(v3)=0 h) deg(v1)=2 , deg(v2)=0 , deg(v3)=1 a tu izomorficzna jest ostatnia trójka.

konpopoz: Dziękuję wszystkim