Information tagen från boken "Diskret matematik" av Lars-Christer Böiers.

Grafteori

Satser

Sats 1 (S. 250)

Låt G = (V, E) vara en graf eller multigraf. Då är
∑(deg(v), v ∈ V) = 2|E|

Sats 2 (S. 255)

Om G är en sammanhängande graf finns det en enkel väg mellan två godtyckliga noder i G.

Sats 3 (S. 260)

Låt G vara en graf med grannmatrisen X.
I matrisen X^p betyder elementet på plats (i, j) antalet olika vägar av längd p mellan nummer i och nod nummer j.

Sats 4 (S. 262)

Sats 5 (S. 268)

Låt G = (V, E) vara en Hamiltongraf. Antag att man tar bort k stycken noder och alla med dessa incidenta bågar. Då har den återstående grafen högst k sammanhängande komponenter. Satsen har som konsekvens att om man i en graf G kan ta bort k noder så att G därvid faller sönder i k+1 eller fler sammanhängande komponenter så kan G inte vara en Hamiltongraf.

Sats 6 (S. 270)

Låt G vara en öglefri graf med n ≥ 3 noder. Antag att det för alla par x,y av noder som inte är grannar gäller
deg(x) + deg(y) ≥ n
Då har G en Hamiltoncykel.

Sats 7 (S. 271)

Låt G = (V, E) vara en öglefri graf med |V| = n ≥ 3. Antag att
deg(x) + deg(y) ≥ n - 1 för alla x,y ∈ V, x ≠ y
Då har G en Hamiltonväg.

Sats 8 (S. 275)

Låt G = (V, E) vara en plan sammanhängande graf. Då är
v - e + r = 2

Sats 9 (S. 281)

En graf är planär om och endast om den inte innehåller någon delgraf som är homeomorf med K₅ eller K_3,3.

Sats 10 (S. 286)

P(G, λ) = P(G - e, λ) - P(G_e, λ)

Sats 11 (S. 287)

För varje graf G med n noder är P(G, λ) ett polynom i λ av grad n med heltalskoefficienter. Koefficienten för λⁿ är 1, den konstanta termen är 0 och koefficienterna har alternerande tecken.

Sats 12 (S. 288)

Låt G vara en graf och a och b noder sådana att e = ab inte är en båge i G. Beteckna med G + e den graf som fås genom att lägga till bågen e i G, och med G_e grafen som bildas då man låter noderna a och b i G sammanfalla (fusion i G + e). Då är
P(G, λ) = P(G + e, λ) + P(G_e, λ)

Sats 13 (S. 289)

Låt G vara en graf med delgrafer G₁, G₂ sådan att
G = G₁ ∪ G₂ och G₁ ∩ G₂ = K_m
för något m. Då är
P(G, λ) = P(G₁, λ) ⋅ P(G₂, λ)
          ──────────────────
                  λ^(m)

Sats 14 (S. 290)

Om G är en planär graf är x(G) ≤ 4.

Sats 15 (S. 295)

En riktad graf G utan isolerade noder är en Eulergraf om och endast om G är sammanhängande och balanserad.