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 $n\ge 3$ vrcholmi taký, že pre stupne ľubovoľnej dvojice nesusedných vrcholov $u,v\in V$ platí

$\text{deg}(u)+\text{deg}(v)\ge n.$

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 $n\ge 3$ vrcholmi, ktorý neobsahuje hamiltonovskú kružnicu, zjavne nemôže byť kompletný, a preto v grafe G existuje dvojica nesusedných vrcholov $x,y\in V$. Zo skutočnosti, že G je maximálny nehamiltonovský graf vyplýva, že po pridaní hrany $e=\{x,y\}$ 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

$(x=v_1,e_2,v_2,\dots ,v_n=y).$

Položme

$A=\{v\in V|\{v,x\}\in E\}$

a

$B=\{v_i\in V|\{v_{i-1},y\}\in E\}.$

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

$|A|+|B|\ge n.$

Vrchol $x=v_1$ však zjavne nepatrí ani do A, ani do B, a preto

$|A\cup B|\le n-1.$

Z uvedených dvoch nerovností potom vyplýva

$|A\cap B|\ge 1,$

čo znamená, že existuje vrchol $v_i$ 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 $x=v_1$ do $v_{i-1}$ po hamiltonovskej ceste grafu G. Zo skutočnosti $v_i\in B$ vyplýva, že $v_{i-1}$ susedí s $y=v_n$, prejdeme teda do $y_n$ a spätným postupom po hamiltonovskej ceste prídeme až do vrchola $v_i$, ktorý, keďže patrí do A, susedí s $x=v_1$. 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 Šablóna:Eng icon.