8. feladatsor megoldása (vázlat) 1. A gráf tartalmaz 3-as klikket, 3 színnel mégsem színezhető, ez könnyen ellenőrizhető (kiindulva az egyik hároszögből). 4 színnel viszont a probléma megoldható, ha a szemben lévő pontpárok színe azonos: 1,5-> 1. szín, 2,6-> 2. stb. 2. G minden színosztályának egy-egy reprezentánsát kiválasztva, és azokat G-ben klikké kiegészítve éppen a megfelelő G' gráfot kapjuk. Így nyilván nem változott a színezési szám, hiszen az eredeti színezés továbbra is jó marad, a klikkszám pedig most már (G'-ben) megegyezik a színezési számmal. 3. A feladat egy olyan gráf színezése, amelynek pontjait a négyzetrács mezőiből kapjuk. Ekkor minden pont fel, le, jobbra és balra össze van kötve a második mezővel, valamint a négy átlós irányban eggyel-eggyel. A gráf két komponensből áll: sakktáblaszerű színezést feltételezve a négyzetrácson fekete és fehér mezők nincsenek összekötve. Így elég az egyik komponenst kiszínezni. A klikkszám 4, pl. az (1,0),(0,1),(1,2),(2,1) pontok K_4-et feszítenek. Egy 4 színnel való színezés pedig: 4 soronként periodikusan: 1 2 1 2 ... 3 4 3 4 ... 2 1 2 1 ... 4 3 4 3 ... 4. Tegyük fel, hogy a gráf valamely színezésében nincs olyan piros színű pont, amelynek a szomszédai között az összes felhasznált pirostól különböző szín előfordul. Ekkor minden piros ponthoz található olyan nem piros szín, amilyen színű szomszédja nincs. Ha minden egyes piros pontot ezekre a most meghatározott színekre színezünk át, akkor a színezés nem romlik el, de ehhez n-1 színt használtunk, ami ellentmondás. 5. Mindkét esetben a kettőhatványok (1,2,4,...,128) teljes részgráfot feszítenek, a klikkszám 8. Az (a) esetben a maximális fokszám 7, ezért a feladat 8 színnel mohó színezéssel is megoldható. A (b) esetben minden számnak legyen a normája a(z egyértelmű) prímfelbontásában a szereplő prímek kitevőinek összege. 128-ig 0,1,...,7 normájú számok fordulnak elő. Az egyes színosztályok legyenek az azonos normával rendelkező számoknak megfelelő pontok halmaza. Ha a valódi osztója b-nek, akkor a normája kisebb, mint b normája, ezért a színezés jó. A krom. szám mindkétszer 8. 6. G minden pontjában k db él találkozik, ezek színe szükségképpen különböző, ezért minden csúcsban minden szín pontosan egyszer fordul elő. Ezért az egyik színosztály élei éppen egy teljes párosítást alkotnak. 7. Egy mérésnek 3 kimenetele lehet, ezért egy mérés (a) esetben sem lehet elég. Esetvizsgálattal ellenőrizhető, hogy két méréssel (b) is megoldható. 8. A mátrixszorzás szabályaiból következik, hogy egy egyszerű gráf szomszádsági mátrixának k-adik hatványának i,j eleme azt mutatja meg, hogy i és j között hány k hosszú élsorozaton lehet eljutni. (Ez k=1-re triviális.) Mivel G összefüggő, minden k-ra lesz olyan két pont, melyek között vezet k hosszú "út", amely lehet, hogy csak élsorozat (pl. ugyanazt az élt többször is használja). Így a mátrixnak lesz nem nulla eleme. 9. Az első mátrixból nem lehet gráfot konstruálni, mert az első két kör felrajzolása után a mátrix harmadik sorának megfelelő kör élei már biztosan nem alkothatnak kört. A másik mátrixnak megfelelő gráf két pont között három párhuzamos él.