— — Věta o sudosti (princip sudosti)

Věta o sudosti (princip sudosti)

∀G = (V, E) : ∑_{v∈V} deg_{G}(v) = 2|E|

DŮKAZ:

Vlevo každá hrana přispěje 2×. Q.E.D.

Důsledek:

∀G: počet vrcholu každého stupně je sudý.

Poznámka:

Neplatí pro nekonečné grafy (o-o-o-o-⋯).

o / “

o ----- o ----- o ----- o

Skóre grafu

G = ({v_{1}, …, v_{n}}, E), skóre grafu G = D(G) = (deg_{G}(v_{1}), …, deg_{G}(v_{n}))

Dvě skóre považujeme za stejná, pokud se liší pouze pořadím prvků.

Příklad:

o / “

o ----- o ----- o ----- o má skóre (1, 2, 2, 2, 3).

o / “ o - o - o - o

k němu není izomorfní.

Věta o skóre:

D = (d_{1}, …, d_{n}, 0 ≤ d_{1} ≤ ⋯ ≤ d_{n})

D je skóre nějakého grafu, právě když

D′ = (d_{1}, …, d_{n−d_{n}−1}, d_{n−d_{n}} − 1, …, d_{n−2} − 1, d_{n−1} − 1)

je skóre nějakého grafu.

Příklady použití:

Je (1, 2, 3, 3, 3, 4, 4) skóre nějakého grafu? (1, 2, 2, 2, 2, 3) skóre nějakého grafu?

— — Skóre grafu

(1, 2, 1, 1, 1)
(1, 1, 1, 1, 2)
(1, 1, 0, 0) ⇔ (0, 0, 1, 1)
(0, 0, 0)

je skóre grafu.

Je (1, 1, 1, 2)?

(1, 0, 0)
(0, 0, 1)
(0, −1)

není.

Je (0, 1, 2, 3, 4, 4)?

(0, 0, 1, 2, 3)
(0, −1, 0, 1)

DŮKAZ:

“⇐”

G′ má skóre D′. Přidáme ke G′ nový vrchol v_{n} a spojíme ho hranou s vrcholy v_{n−1}, v_{n−2}, …, v_{n−d_{n}}. Dostáváme tak graf se skóre D.

“⇒”

Předpokládáme, že G = ({v_{1}, …, v_{n}}, E) má skóre D. Označme d = d_{n} = degv_{n}. První případ: Z v_{n} vedou hrany do vrcholů v_{n−1}, v_{n−2}, …, v_{n−d}. Odstraněním

v_{n} pak z těchto hran dostaneme graf se skóre D′.

Druhý případ: Neplatí první případ, tedy potom je vrchol v_{n} propojen s jinými vrcholy, než je posledních d_{n}, neboli:

i < n − d ≤ j : {v_{i}, v_{n}} ∈ E, {v_{j}, v_{n}} ∉ E

Ale protože degv_{i} (= d_{i}) ≤ degv_{j} (= d_{j}), existuje v_{k} (k ≠ i, j) takový, že {v_{j}, v_{k}} ∈ E, {v_{i}, v_{k}} ∉ E (tedy existuje zase nějaký vrchol v_{k} takový, který je spojený s v_{j}, ale ne v_{k} a tím se stupeň kompenzuje).

Přidáme do E hrany {v_{i}, v_{k}}, {v_{j}, v_{n}}, odebereme z E hrany {v_{i}, v_{n}}, {v_{j}, v_{k}}. Skóre tak zůstává D, ale zmizela neposedná hrana mimo posledních d_{n} prvků (vrcholy v_{i}, v_{j} jsme místo přes v_{n} spojili přes v_{k}). Převedli jsme tedy situaci na první případ.

Q.E.D.