Dokazy

Question 1

cesta <=> sled

Question 2

most <=> neleži na kružnici

Question 3

n-c≤m≤1/2(n-c)(n-c+1)

Question 4

rad(G)≤diam(G)≤2rad(G)

Question 5

Matica susednosti (3 odražky)

Question 6

Graf je centrom nejakeho suvisleho grafu

Question 7

Centrom stromu je K1 alebo K2

Question 8

Graf je periferiou suvisleho grafu akk ecc =1 alebo≠1

Question 9

Kappa ≤ delta

Question 10

Kappa’ < delta

Question 11

Kappa ≤ kappa’

Question 12

pre p,q,r vieme najst graf s kappa,kappa’,delta

Question 13

2-suvisly <=> 2 vrcholy ležia na spol kružnici

Question 14

Hnusna veta o postupnosti a suvislosti

Question 15

Bloky su disjunktne alebo artikulacia

Question 16

S je NZ , V-S je Pokrytie

Question 17

Alfa + beta = n

Question 18

alfa ≥ 1/1+deg

Question 19

Alfa’ + beta’ =n

Question 20

Sparenie je najväčšie <=> neobsahuje M-rozsir cestu

Question 21

Hallova veta

Question 22

M=K tak m je max a k je min

Question 23

Bip alfa’ = beta

Question 24

Erdos sekeres r(k,l)

Question 25

R(k,l) odhad cez kombinacne

Question 26

Dosledok r(k,l) cez kombinacne

Question 27

Turanov graf ma najviac hran z k-part

Question 28

Graf neobsahujuci kliku k+1 ma menej ako turanov

Question 29

Farbenie je 2 <=> neobs neparnu kruznicu

Question 30

Farbenie a bloky

Question 31

Farbenie a min stupen podgrafu

Question 32

Farbenie, 1+ delta

Question 33

Farbenie brooks

Question 34

Farbenie a nezavislost

Question 35

Farbenie x+x, xx, nordhaus

Question 36

Hranove farbenie, kompletny graf

Question 37

Hranove farbenie, bipartitny

Question 38

Chromaticky polynom rekurzia

Question 39

Turnaj obsah hamiltonovsku drahu

Question 40

Turnaj obsahuje cyklus, tak aj cyklus 3

Question 41

Turnaj je silne suvisly, potom cykly 3 až n