Motivering varför det kromatiska talet är det minsta möjliga
Hej!
Min lärobok och föreläsare lyfter fram att steg (ii) är väldigt viktigt när man påstår att en graf har det kromatiska talet :
Jag har haft problem specifikt med nedanstående graf, som man i facit visar har :
Jag kom fram till samma sak kring den nedre gränsen för kromatiska talet, men sedan försökte jag skissera något form av bevis eftersom man förväntas "show that there is no coloring with fewer than colors". Jag kom ingen riktig vart. Tycker inte facit är så formellt, osäker på om en sådan kortfattad motivering skulle godkännas på en tentamen...
Kan någon ge ett förslag på hur jag skulle kunna motivera att för denna graf?
Tack!
Facits resonemang går att förtydliga lite. Typ
1. Yttre cykeln är udda => kräver tre färger
2. Anta att inre skulle gå att färga i bara 1 och 2, då kan du inte ha någon diagonal mellan 1 och 2, för det skulle utesluta båda färger, men det måste du ha om färgerna används på större avstånd än 1 ifrån varandra.
3. Den inre har tre färger runt sig, måste anv en fjärde.
