Mam jeszcze dwa zadanka:
1. Pokaż, że graf z n wierzchołkami i q kantami ma przynajmniej n-q składowych.
2. Pokazać, że suma prosta grafów G1 + G2 ma regularność k1+k2, gdy grafy G1 i G2 mają odpowiednio regularności k1 i k2.
Suma prosta grafów to:
G1 =(V1,E1) i G2=(V2,E2). Zbiór wierzchołków jest równy V1 x V2. A wierzchołki (v1,w1) i (v2,w2) są dokładnie połączone, gdy v1=v2 i w1w2 należy do E2
albo v1v2 należy do E1 i w1=w2.
Dziękuję za wszelką pomoc.