Feladat: B.4218 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Ágoston Tamás ,  Damásdi Gábor ,  Éles András ,  Mester Márton ,  Mészáros András ,  Strenner Péter 
Füzet: 2010/május, 284 - 285. oldal  PDF file
Témakör(ök): Feladat, Gráfelmélet
Hivatkozás(ok):Feladatok: 2009/november: B.4218

Mekkora lehet a legrövidebb kör hossza egy olyan gráfban, amelyben egyetlen csúcs sincs összekötve az összes többivel, bármely két éllel össze nem kötött csúcsnak van közös szomszédja, és ha a csúcsok számát n-nel jelöljük, akkor a fokszámok négyzetösszege n2-n?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Megoldás. Legyenek a gráf csúcsai A1,A2,...,An, az Ai fokszámát jelölje ai. Az Ai-vel szomszédos csúcsok halmaza Bi, az Ai-vel nem szomszédos csúcsoké pedig Ci. A feladat feltétele szerint Ci minden elemének létezik szomszédja Bi-ben. Ezért a Bi-beli csúcsok fokszámának összege legalább |Bi|+|Ci|=n-1. Ezeket az értékeket i=1-től n-ig összegezve legalább n(n-1)-et kapunk. Ebben az összegben minden csúcs annyiszor szerepel, amennyi a foka, így

n2-n=a12+a22+...+an2n(n-1).
Mivel itt egyenlőség van, valamennyi becslésben egyenlőség teljesül, azaz minden Ci-beli csúcsnak pontosan egy Bi-beli szomszédja van, és semelyik két Bi-beli csúcs nincs egymással összekötve. Ez úgy is fogalmazható, hogy a gráf tetszőleges csúcsának semelyik két szomszédja között nem halad él. Ebből következik, hogy a gráf nem tartalmaz 3-hosszúságú kört. Így azonban 4-hosszúságú kör sem lehet benne. Ha ugyanis A1, A2, A3, A4 egy ilyen kör csúcsai az összekötés sorrendjében, akkor ‐ 3-hosszúságú kör nem lévén ‐ A3C1, A2,A4B1, és A3-nak két szomszédja is van B1-ben: A2 és A4, ami ellentmondás. A legrövidebb kör hossza tehát legalább 5. Ha a gráf egyetlen 5-hosszúságú kör, akkor teljesül a feladat valamennyi feltétele; a legrövidebb kör hossza tehát lehet 5. Megmutatjuk még, hogy a legrövidebb kör sosem lehet 5-nél hosszabb. Egy 5-nél hosszabb legrövidebb A1A2,...,Ak-1Ak (k6) körben ugyanis például az egymással össze nem kötött A1 és A4 csúcsoknak nincs közös szomszédja; ha ugyanis P mindkettőjükkel össze lenne kötve, akkor A1A2A3A4P 5-hosszúságú kör lenne, ami ellentmondás. Így viszont a gráf nem teljesítené a feladat egyik feltételét.
A legrövidebb kör hossza tehát csakis 5 lehet.