ZASADA WŁĄCZANIA I WYŁĄCZANIA

=

| | −

− ⋯ + (−1)

…

W szczególności

= | | + | | −

DOWÓD szczególnego przypadku

Zbiory A-B, A ⋃ , B-A są parami rozłączne

( − )

(

)

( − ) =

Stąd

= ( − )

(

)

( − ) = | − | +

+ | − |

Stąd

+

= | − | +

+ | − | +

= | − | +

+ | − | +

= ( − )

(

) + ( − )

(

) = | | + | |

A stąd otrzymujemy

= | | + | | −

Co kończy dowód
TWIERDZENIE: Każda mapa może być pokolorowana pięcioma kolorami
DOWÓD: Udowodnimy, że każdy graf planarny da się pokolorować na pięć kolorów (po
wierzchołkach)
Indukcja względem liczby wierzchołków:
1Dla ≤ 5 jest to prawda
23. Niech G będzie grafem planarnym o liczbie wierzchołków n>5. Zakładam, że grafy planarne o ilości
wierzchołków mniejszej niż n mogę pokolorować przy pomocy pięciu kolorów.
4

∑

( ) = 2| | ≤ 6| | − 12 ≤ 6| |

Z tego wynika, że istnieje wierzchołek v o stopniu co najwyżej 5
Tworzę podgraf G’ grafu G poprzez usunięcie wierzchołka v i krawędzi do niego incydentnych z
grafu G. Graf G’ jest planarny i ma mniej wierzchołków niż G, stąd z założenia indukcyjnego mogę go
pokolorować przy użyciu pięciu kolorów.
Koloruję G’ na 5 kolorów.
Jeśli któryś z pięciu kolorów nie został użyty przy kolorowaniu G’, to mogę go użyć do pokolorowania
wierzchołka v w grafie G i mam w nim pięć kolorów
Dla wszystkich 1 ≤ < ≤ 5 oznaczamy przez

,

podgraf G utworzony przez wierzchołki

pokolorowane kolorami i i j oraz krawędzie między nimi
Np.

,

Jeśli wierzchołki , należą do różnych składowych spójności grafu

,

, to w składowej zawierającej

zamieniamy kolory. Wtedy zyskujemy jeden „wolny” kolor do pokolorowania wierzchołka v

Jeśli wierzchołki należą do tej samej składowej spójności grafu

,

, to

,

Jeśli wierzchołki , są z tej samej składowej spójności co , , to muszą się przeciąć, co oznacza
sprzeczność z tym, że graf G jest planarny
Dowód tw. Halla dla wersji małżeńskiej
<= Jeśle jest spełniony warunek Hall, to każda dziewczyna znajdzie męża.
Indukcja ze względu na m-ilość dziewczyn
1M=1 – oczywiste
2Zakładamy, że stwierdzenie jest prawdziwe dla m dziewcząt, gdzie m>1, czyli dziewcząt 1,…,m może
znaleźć sobie mężów, niech to będą chłopcy 1

I

,…,m

I

3Weźmy dziewczynę m+1 – czy znajdzie męża ? – musimy pokazać, że tak
J4eśli m+1 zna jakiegoś innego chłopaka niż 1

I

,…,m

I

, to tego chłopaka może wziąć za męża.

Dziewczyna m+1 zna tylko chłopców 1

I

,…,m

I

.

Dziewczyna m+1 urządza przyjęcie. Zaprasza na nie wszystkich chłopców których zna 1

I

,…,i

I

. Ci chłopcy

biorą na przyjęcie swoje żony 1,…,i. Dziewczyny 1,…,i zapraszają chłopców, których znają
(m+1) -> (1

I

,…,i

I

) -> (1,…,i) -> ( (i+1)

I

,…,k

I

) ->((i+1),…,k) -> (…,c,…)

A których jeszcze nie ma na przyjęciu, ( (i+1)

I

,…,k).

Oni biorą swoje żony itd. Aż do momentu, w którym pojawi się chłopak c, który nie ma żony. Musi się
pojawić, bo jest spełniony warunek Halla.
Chłopak c tańczy z dziewczyną, która go zaprosiła, powiedzmy p. Dziewczyna p przyszła z chłopakiem p

I

(c,p) ->(p

I

, r) -> … -> (s

I

,t) -> (t

I

,m+1)∈ (1

I

,…,i

I

)

Który tańczy z dziewczyną r.
Każda dziewczyna znalazła męża.



12.Twierdzenie chińskie o resztach + dowód.
Niech m

1

,m

2

,...,m

n

będą dodatnimi liczbami względnie pierwszymi,tzn dla każdej pary 1<=i<=j<=r mamy

NWD(m

i

,m

j

)=1,oraz niech a

1

,a

2

,...a

r

będą dowolnymi resztami.Wtedy istnieje liczba całkowita a,taka

że:a

1

=a(mod m

1

),a

2

=a(mod m

2

),...,a

r

=a(mod m

r

)

Dowód:
Niech M=m

1

*m

2

*...*m

r

,m

i

,m

j

są względnie pierwsze dla każdego 1£i<j£r

"1£i£r M/m

i

,m

i

-względnie pierwsze,czyli NWD(M/m

i

,m

i

)=1.

W takim razie $x

i

,y

i

: x

i

*M/m

i

+y

i

*m

i

=1.

To z kolei oznacza,że M/m

i

*x

i

º1(mod m

i

), 1£i£r.

M/m

i

jest podzielne bez reszty przez m

j

,j¹i,czyli M/m

i

*x

i

º0(mod m

j

)

Mnożymy przez a

i

M/m

i

*x

i

*a

i

ºa

i

(mod m

i

) dla j¹1 M/m

i

*x

i

*a

i

º0(mod m

j

)

Weźmy:aº(M/m

1

*x

1

*a

1

+M/m

2

*x

2

*a

2

+...+M/m

r

*x

r

*a

r

)(mod m

1

)

aºM/m

1

*x

1

*a

1

(mod m

1

)

aº M/m

2

*x

2

*a

2

(mod m

2

)

aº(M/m

1

*x

1

*a

1

+M/m

2

*x

2

*a

2

+...+M/m

r

*x

r

*a

r

)(mod m

r

)

aº M/m

r

*x

r

*a

r

(mod m

r

)

W takim razie "1£i£r aº(M/m

i

*x

i

*a

i

)(mod m

i

)

Załóżmy teraz,że "1£i£r jest a

i

ºa(mod m

i

) oraz a

i

ºb(mod m

i

) ,b¹a

Odejmujemy stronami:0º(a-b)(mod mi),czyli każda z liczb mi dzieli (a-b)
Ponieważ liczby m

1

,...,m

r

–względnie pierwsze,więc ich iloczyn czyli M również dzieli (a-b)Þa-b różnią się

o krotność M.
16.Lemat o uściskach dłoni + dowód.
Niech G będzie grafem prostym.Wówczas deg(v

1

)+...+deg(v

n

)=2m

Dowód:1)Jeśli m=0,to równość jest prawdziwa 2)Zakładamy,że lemat zachodzi dla m³0 3)Udowodnimy
równanie dla m+1.Niech eÎE(G) będzie dowolną krawędzią.Z zał.ind. wiadomo,że
deg(v

1

)+...+deg(v

n

)=2m*(G-e),gdzie deg(v

1

) jest stopniem v1 w grafie G-e.Dla grafu G suma stopni

wierzchołków jest o 2 większa niż dla G-e oraz m(G)=m(G-e)+1,co oznacza,że równanie zachodzi dla
grafie G o m+1 krawędziach.
Twierdzenie Orego o grafach hamiltonowskich

Dowód: Załóżmy, że istnieją grafy spełniające warunek (Jeżeli dla każdych dwóch nie sąsiednich
wierzchołków grafu G suma ich stopni jest nie mniejsza niż ilość wszystkich wierzchołków w G,
to G jest hamiltonowski. *) ale nie hamiltonowskie. Wybieramy maksymalny (ze względu na ilość
krawędzi) taki graf G, który spełnia (*), nie jest hamiltonowski, ale po dodaniu krawędzi stanie się
hamiltonowski. W grafie G jest ścieżka hamiltona.

(v1) = {v2,

,...,

}

~

( 1)={

,…

}

Zauważmy, że (**) (v1)

∩ (vn)≠ ∅

Dowód (**)
Przypuśćmy, że

~

( 1) ∩ (vn)=∅

Wtedy

~

( 1) ∪ (vn)≤{v2,v3,...,vn}

|

~

( 1) ∪ (vn)|≤n-2|

~

( 1) + (vn)|≤n-2 (v1)-1+ (vn)≤n-2 (v1)+ (vn)≤n-1

W takim razie

~

( 1) +

(vn)

≠ ∅ => ∃ ∈

~

( 1) ^ ∈

(vn)

∈ (v1) ∈

(vn)

Cykl Hamiltona w grafie G: (v1,v2,...,vil,vn,vn-1,...,vil+1,v1)

Twierdzenie Kóninga
Jeżeli G jest dwudzielny to

(G)=

∆

Dowód: Niech G-graf dwudzielny
*krawędzie są „pomiędzy” zbiorami podwału
*w grafie dwudzielnym wszystkie cykle jakie istnieją są parzyste
Dowód indukcyjny ze względu na ilość krawędzi (m) w G
(1) m=0,

∆=0, =0=∆ m=1, ∆=1, =1=∆ (2) zakładamy, że dla każdego grafu dwudzielnego G’ o

1<m’<m krawędziach (G’)=

∆ (3) niech G-graf dwudzielny o m krawędziach

Tworzymy G’ usuwając dowolną krawędź czyli

(G’)=

∆ - czyli krawędź w G’ można pokolorować na

∆ kolorów Czy graf G można pokolorować w ∆ kolorów?

( )= ( )-1≤ ∆-1 ( )= ( )-1≤ ∆-1(a) przy wierzchołku u brakuje koloru c; przy wierzchołku

v brakuje tego samego koloru c. Wtedy kolorem c kolorujemy krawędź uv, mamy pokolrowanie G w

∆

kolorów (b) przy wierzchołku u brakuje koloru c, a przy v brakuje koloru c’. Rozważmy najdłuższą
ścieżkę wychodzącą z wierzchołka u, w której znajdują na przemian krawędzie pokolorowane kolorami c
i c’. W ścieżce wychodzącej od wierzch. U zauważamy kolory c

↔c’. W wyniku tego przy wierzchołku u

i v brakuje tego samego koloru c’. Kolorujemy tym kolorem krawędź uv i mamy kolorwanie grafu G w

∆

kolorów.

Twierdzenie Eulera-Nierholtza

Niech G-graf spójny. Następujące własności są równoważne:
-każdy wierzchołek w G ma st. parzysty
-istnieje p cykli c1...cp takich, że każda krawędź grafu G należy do dokładnie jednego cyklu (G można
przedstawić jako sumę rozłącznych krawędziowo cykli)
-G nie jest Eulerowski
Dowód: ''1=>2'' Indukcja ze względu na c-ilość cykli w grafie G
1.

C=1 (rysunek szesciokątu foremnego) G=Cn

2.

Zakładamy, że stwierdzenie zachodzi dla każdego grafu G' o c' cyklach (jeśli każdy

st. wierzchołka w grafie G' jest parzysty, to G' można przedstawić w postaci sumy krawędziowo
rozłącznych cykli)
3.

Niech G-graf o c cyklach 1<c'<c, każdy wierzchołek G ma st. parzysty Tworzymy

G' usuwając z grafu G krawędzie dolnego cyklu. Z założenia indukcyjnego G' można podzielić na
rozłączne krawędziowo cykle => G też można
''2=>3''
1.

c=1 G=Cn

2.

Zakładając, że stwierdzenie jest prawdziwe dla każdego G' o c' cyklach 1<c'<c

(jeśli G' można podzielić na rozłączne krawędziowo cykle, to w G' można znaleźć domknięty szlak
Eulera)
3.

Niech G-graf, który można podzielić na c rozłącznych krawędziowo cykli i c>1

Cyklegrafu G numerujemy w ten sposób, że (rysunek 7 kół)
Tworzymy graf G' usuwając z G krawędzie ostatniego cyklu (p-tego). Graf G' spełnia zał. indukcyjne,
więc w G' istnieje zamknięty szlak Eulera:(v1,...vn,v1) Dodajemy do G' krawędzie p-tego cyklu.
Szukamy zamkniętego szlaku Eulera w G.
(v1,....,vi,.....vj,vi,....,vn,v1)
1 2 3
1.

idziemy po wierzchołkach ze szlaku Eulera z grafu G' aż do napotkania

wierzchołka vi bnależącego do cyklu p-tego
2.

przechodzimy po krawędziach p-tego cyklu

3.

3. część szlaku eulera w G'

„3=>1' Jeśli G jest Eulerowski to każdy wierzchołek ma stopień parzysty.