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

${\textrm {deg}}(u)+{\textrm {deg}}(v)\geq 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\geq 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},\ldots ,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|\geq n.$

Vrchol $x=v_{1}$ však zjavne nepatrí ani do A, ani do B, a preto

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

Z uvedených dvoch nerovností potom vyplýva

$|A\cap B|\geq 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 (po anglicky).