Jonahs stora seriösa sats
Jonahs Stora Seriösa Sats är en av de två seriösa satser Jonah har formulerat. Det är okänt om den redan existerar under ett annat namn.
Jonahs Stora Seriösa Sats är en generalisering av Jonahs Lilla Seriösa Sats.
Innehåll
Definitioner
- En tre-dimensionell graf är en hörn-, kant- och regionmängd där varje kant är ett oordnat par av två hörn i grafen och varje region är en kantcykel (men en kantcykel måste inte vara en region). Med en "tre-dimensionell" graf menas att grafen bör observeras och hanteras i rummet istället för i planet då det är lättare att föreställa sig de definitioner och formuleringar som beskrivs nedan.
- En "stängd" tre-dimensionell graf är en tre-dimensionell graf sådan att det inte existerar någon väg över regionerna, där en väg endast får korsa kanterna, som gör att man når andra sidan av en region.
- En "triangulär region" är en region vars kantcykels längd är exakt tre.
- En "tom" tre-dimensionell graf är en tre-dimensionell graf sådan att ingen kant gränsar till 3 eller fler regioner.
- En "komponent" av en tre-dimensionell graf är en mängd hörn som inte är sammanbundna med något annan hörn i grafen.
- [math]\displaystyle \deg r[/math] är graden för regionen r, det vill säga antalet kanter regionens kantcykel har.
Satsen
Låt G vara en stängd, tom tre-dimensionell graf bestående av endast triangulära regioner. Då går det att för varje komponent i grafen ordna in samtliga regioner i par, där varje region tillhör exakt ett par och de båda regionerna i ett par delar exakt en kant. Målet med detta är att kunna ta bort kanten varje regionpar delar, så att nya regioner bildas där [math]\displaystyle \deg r'=4[/math] för varje ny region [math]r'\in R'[/math] (det vill säga att regionerna blir till fyrhörningar istället för en trianglar). Denna process kommer framöver att kallas för quadifiering (fr. eng. quadifying).
Bevis
För att föreställa sig de processer som visas här kan det vara fördelakigt att projicera den tre-dimensionella grafen på ett liknande sätt som framställs i beviset för Jonahs Lilla Seriösa Sats. Härdanefter i beviset kommer [math]\displaystyle G[/math] att innebära "en godtycklig komponent ur [math]\displaystyle G[/math]".
Konstruera en ny graf [math]\displaystyle H[/math] där varje region i [math]\displaystyle G[/math] motsvaras som ett hörn i [math]\displaystyle H[/math]. Förbind sedan med kanter de hörn i [math]\displaystyle H[/math] vars motsvarigheter i [math]\displaystyle G[/math] delar en kant. Eftersom varje region i [math]\displaystyle G[/math] är triangulär och gränsar till exakt tre andra regioner gäller att [math]\displaystyle \deg v=3, \forall v\in H[/math]. Antag nu att [math]\displaystyle H[/math] har en separerande kant. Det motsvaras i [math]\displaystyle G[/math] av två kantdelande regioner vars hörnmängder på var sida inte är sammanbundna genom någon annan väg än genom kanten regionerna delar. Titta nu på den kant i [math]\displaystyle G[/math] dessa regioner delar, dvs. den som den separerande kanten i [math]\displaystyle H[/math] "korsar". Uppenbarligen finns det regioner på var sida om denna kant enligt förutsättningarna. Men eftersom dessa regioner inte är sammanbundna utom genom den nämnda kanten kommer det totala antalet yttre kanter, kanter som gränsar till det oändliga området utanför grafen, vara minst fyra, vilket motsäger [math]\displaystyle \deg r=3, \forall v\in G[/math] för regionen som identifierats med det oändliga området utanför grafen enligt projiceringen. Alltså saknar [math]\displaystyle H[/math] separerande kanter.
Välj nu en godtycklig delmängd [math]\displaystyle X[/math] av hörnmängden i [math]\displaystyle H[/math]. Välj sedan en godtycklig komponent [math]\displaystyle H_K[/math] ur den inducerade delgrafen [math]\displaystyle H\backslash X[/math] som bara har ett udda antal hörn. Titta sedan på antalet kanter som förbinder [math]\displaystyle H\backslash X[/math] med [math]\displaystyle H_K[/math]. Vi delar därefter upp detta i tre distinkta fall:
(I) Antag att antalet är 0. Detta är uppenbarligen omöjligt, eftersom vi har separerat [math]\displaystyle G[/math] i komponenter. [math]\displaystyle \rightarrow \leftarrow[/math]
(II) Antag att antalet är 1. I sådana fall är detta en separerande kant, vilket enligt lemmat ovan ger motsägelse. [math]\displaystyle \rightarrow \leftarrow[/math]
(III) Antag att antalet är 2. Vi kan skriva att den valda komponenten har udda antal hörn som [math]\displaystyle |H_K|=2k+1,k\ge 0[/math]. Enligt förutsättningarna ovan vet vi dock också att [math]\displaystyle \deg v=3, \forall v\in H_K[/math], vilket ger [math]\sum_{v \in H_K} \deg v = 3(2k+1)[/math]. Låt oss nu plocka bort de två kanterna som förbinder [math]\displaystyle H_K[/math] med [math]\displaystyle H[/math]. Vi har nu en individuell graf vars nya gradsumma är [math]\sum_{v \in H_K'} \deg v = 3(2k+1)-2[/math] vilket är udda. Men detta motsäger [math]\sum_{v \in V} \deg v = 2|E|[/math], dvs. att gradsumman skall vara jämn.[math]\displaystyle \rightarrow \leftarrow[/math]
Nu har vi visat att antalet kanter som förbinder en godtycklig [math]\displaystyle H_K[/math] med [math]\displaystyle H[/math] är minst tre. Antag nu att [math]\displaystyle Antal(H_K)\gt |X|[/math], dvs. att antalet komponenter i [math]\displaystyle H\backslash X[/math] med udda antal hörn är fler än antalet hörn i [math]\displaystyle X[/math]. Men en sådan komponent [math]\displaystyle H_K[/math] kräver ju minst tre kanter som förbinder den med [math]\displaystyle X[/math] som visat ovan, dvs. att det totala antalet sammanbindande kanter är [math]\displaystyle |E|=3\cdot Antal(H_K)\gt 3|X|[/math], vilket ger motsägelse eftersom [math]|E|=\frac{1}{2}\sum_{v \in X} \deg v = \frac{1}{2}\cdot 3|X|[/math].[math]\displaystyle \rightarrow \leftarrow[/math]
Nu har vi visat att alla förutsättningar för att tillämpa Tuttes sats är uppfyllda, och vi erhåller att det existerar en perfect matchning i [math]\displaystyle H[/math]. Detta innebär att det finns ett sätt att i [math]\displaystyle H[/math] ordna in samtliga hörn i par, så att varje hörn delar en kant och att varje hörn ingår i exakt ett par. Det leder till att vi kan ordna in samtliga regioner i [math]\displaystyle G[/math] så att varje region delar en kant och att varje region ingår i exakt ett par, vilket skulle visas.
