Oreho veta

Oreho veta je matematické tvrdenie hovoriace o postačujúcej podmienke existencie hamiltonovskej kružnice v grafe. Vetu sformuloval v roku 1961 nórsky matematik Øystein Ore.

Znenie vety 

Nech G = (V,E) je neorientovaný graf s  vrcholmi taký, že pre stupne ľubovoľnej dvojice nesusedných vrcholov  platí

Potom G obsahuje hamiltonovskú kružnicu.

Dôkaz 

Sporom. Predpokladajme, že existuje graf G = (V,E) spĺňajúci podmienku zo znenia vety, ktorý hamiltonovskú kružnicu neobsahuje. Ďalej predpokladajme, že G je čo do počtu hrán maximálny graf o n vrcholoch s touto vlastnosťou, t. j. po pridaní ľubovoľnej hrany v grafe vznikne hamiltonovská kružnica.

Graf s  vrcholmi, ktorý neobsahuje hamiltonovskú kružnicu, zjavne nemôže byť kompletný, a preto v grafe G existuje dvojica nesusedných vrcholov . Zo skutočnosti, že G je maximálny nehamiltonovský graf vyplýva, že po pridaní hrany  do E dostávame hamiltonovský graf. Každá hamiltonovská kružnica v tomto grafe musí nutne obsahovať hranu e, pretože inak by bol aj graf G hamiltonovský.
Z toho vyplýva, že G obsahuje hamiltonovskú cestu

Položme

a 

Keďže x a y sú nesusedné, z predpokladu vety vyplýva

Vrchol  však zjavne nepatrí ani do A, ani do B, a preto

Z uvedených dvoch nerovností potom vyplýva 

čo znamená, že existuje vrchol  patriaci súčasne do A aj do B. Potom však môžeme v grafe G skonštruovať hamiltonovskú kružnicu nasledujúcim spôsobom: z  do  po hamiltonovskej ceste grafu G. Zo skutočnosti  vyplýva, že  susedí s , prejdeme teda do  a spätným postupom po hamiltonovskej ceste prídeme až do vrchola , ktorý, keďže patrí do A, susedí s . Prechodom do x tak je možné hamiltonovskú kružnicu uzatvoriť.

Existencia tejto kružnice je však v spore s predpokladom, že G nie je hamiltonovský. Tvrdenie je tak dokázané.

Literatúra 

 Cameron, P.J.: Combinatorics: Topics, techniques, algorithms. Cambridge University Press, 1994.

Externé odkazy 

 Znenie Oreho vety - Wolfram MathWorld .

Teória grafov