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.