Citat:
Ursprungligen postat av dbshw
Ja, för att det finns fler än λ-2 val för antingen det nedre högra eller det övre högra hörnet.
Låt mig förklara. Kalla hörnen i grafen för
ABC
DEF
i den ordningen.
Säg att vi har λ färger att tillgå, och ska färglägga grafen. Säg att vi redan har gett A, B, D och E färger, och ska räkna hur många val vi har för C och F.
Låt oss börja med C. (Det spelar förstås ingen roll vilken av C eller F vi börjar med, utan svaret blir samma.) C får inte ha samma färg som B, men det är också den enda begränsningen, eftersom vi inte har valt färg för F än. Vi har alltså λ-1 val för vilken färg vi ska ge C.
Nu till F. F får inte ha samma färg som C eller E. Beroende på vilken färg vi valde till C, så finns det två fall:
Fall 1: Vi valde en färg på C som E. Det finns alltså bara en förbjuden färg för F, så vi har λ-1 val för F.
Fall 2: Vi valde olika färger på C och E. Nu finns det två färger som är förbjudna, det finns λ-2 val för F.
Det är bara en färg på C som ger fall 1, så fall 1 svarar mot totalt 1*(λ-1) val för färgerna på C och F, givet att ABDE redan är valda.
Resten av de möjliga färgerna för C, dvs λ-2 val för C, ger fall 2, så fall 2 svarar mot totalt (λ-2)(λ-2) val för färger på C och F.
Totalt får vi alltså
λ(λ-1)(λ-2)(λ-3) * (1*(λ-1) + (λ-2)*(λ-2))
(Argumentet ovan gäller bara för λ >= 2, men eftersom vi vet att kromatiska polynomet är ett polynom följer att formeln även stämmer för λ = 1 och λ = 0.)
Låt mig förklara. Kalla hörnen i grafen för
ABC
DEF
i den ordningen.
Säg att vi har λ färger att tillgå, och ska färglägga grafen. Säg att vi redan har gett A, B, D och E färger, och ska räkna hur många val vi har för C och F.
Låt oss börja med C. (Det spelar förstås ingen roll vilken av C eller F vi börjar med, utan svaret blir samma.) C får inte ha samma färg som B, men det är också den enda begränsningen, eftersom vi inte har valt färg för F än. Vi har alltså λ-1 val för vilken färg vi ska ge C.
Nu till F. F får inte ha samma färg som C eller E. Beroende på vilken färg vi valde till C, så finns det två fall:
Fall 1: Vi valde en färg på C som E. Det finns alltså bara en förbjuden färg för F, så vi har λ-1 val för F.
Fall 2: Vi valde olika färger på C och E. Nu finns det två färger som är förbjudna, det finns λ-2 val för F.
Det är bara en färg på C som ger fall 1, så fall 1 svarar mot totalt 1*(λ-1) val för färgerna på C och F, givet att ABDE redan är valda.
Resten av de möjliga färgerna för C, dvs λ-2 val för C, ger fall 2, så fall 2 svarar mot totalt (λ-2)(λ-2) val för färger på C och F.
Totalt får vi alltså
λ(λ-1)(λ-2)(λ-3) * (1*(λ-1) + (λ-2)*(λ-2))
(Argumentet ovan gäller bara för λ >= 2, men eftersom vi vet att kromatiska polynomet är ett polynom följer att formeln även stämmer för λ = 1 och λ = 0.)
Du, jag hajade!

Tack så mycket!
Om en sådan kommer på ett prov så kan jag lika gärna tagit bort 3 kanter va(Jobbigare, men säkrare)?
Löste två stycken nu, men fastnade på c-uppgiften!
Svaret är "x(x-1)(x-2)(x^5-7x+7)" och jag fick "x(x-1)(x-2)(x-3)(x-4)+2x(x-1)(x-2)(x-3)+2x(x-1)(x-2)" så jag kan inte vara så långt ifrån!
Min lösning:http://dl.dropbox.com/u/8776433/2012...2016.22.40.jpg
Kunde inte ladda upp nån bild så fick köra dropbox.
Hoppas du kan se bilden!
, vilken är den andra då?