Grafer, färgning och matchning

En Eulerkrets går genom varje kant exakt en gång. En Hamiltoncykel besöker varje nod exakt en gång innan den återvänder. Det första avgörs av grader i en sammanhängande graf; någon motsvarande enkel gradkarakterisering finns inte för Hamiltoncykler. En graf är bipartit när noderna kan delas i två mängder så att varje kant går mellan mängderna, vilket är ekvivalent med att inga udda cykler finns.

$$\sum_{v\in V}\deg(v)=2|E|$$

Det kromatiska polynomet $P_G(\lambda)$ räknar godkända hörnfärgningar ur en palett med $\lambda$ särskiljbara färger när $\lambda$ är ett icke-negativt heltal. Grannar ska ha olika färger, men färger får lämnas oanvända. Det kromatiska talet är det minsta positiva palettantal som ger en färgning för en icke-tom graf. Ett polynomvärde svarar därför inte direkt på en fråga som kräver att exakt alla givna färger används.

Varje nod har grad två och grafen är sammanhängande. Därför är cykeln själv en Eulerkrets. Samma cykel besöker varje nod en gång och är också en Hamiltoncykel. Genom att färga växelvis med två färger får vi en korrekt färgning; eftersom det finns kanter behövs minst två färger. Om vi i stället hade fem noder skulle växelfärgningen misslyckas vid sista kanten.

$$\chi(C_6)=2,\qquad\chi(C_5)=3$$

Betrakta en fyrhörning med en diagonal mellan två motsatta hörn. Färga diagonalens första ändpunkt på $\lambda$ sätt och den andra på $\lambda-1$ sätt. Vart och ett av de två återstående hörnen gränsar till båda dessa ändpunkter och har $\lambda-2$ val. De återstående hörnen är inte grannar, så valen är oberoende. Därför är $P_G(\lambda)=\lambda(\lambda-1)(\lambda-2)^2$. Med fyra tillgängliga färger finns $4\cdot3\cdot2^2=48$ godkända färgningar.

För att matcha alla noder på ena sidan i en bipartit graf räcker det inte att varje nod har en granne. Flera noder kan konkurrera om för få gemensamma grannar. Halls sats kräver att varje delmängd på den sidan har minst lika många grannar som element. Vid ett bevis väljer du därför en godtycklig delmängd och visar olikheten; att kontrollera enstaka noder bevisar bara specialfall.

$$\forall S\subseteq X:\ |N(S)|\ge|S|$$

Ta bort en kant $e$. I färgningarna av $G-e$ har kantens ändpunkter antingen olika färger eller samma färg. De olika motsvarar precis färgningarna av $G$. De lika motsvarar färgningar där ändpunkterna identifieras till ett hörn, alltså av $G/e$. Därför är $P_G(\lambda)=P_{G-e}(\lambda)-P_{G/e}(\lambda)$. Om hela en palett på $k$ färger måste användas räknar vi bort färgningar som missar färger med inklusion–exklusion: $\sum_{j=0}^{k}(-1)^j\binom kjP_G(k-j)$. För fyrhörningen med diagonal och fyra givna färger blir detta $48-4\cdot6=24$, eftersom triangeln utesluter färgningar med färre än tre färger.