Problem B. 4218. (November 2009)
B. 4218. In a graph, no vertex is connected to all of the others. For any pair of vertices not connected there is a vertex adjacent to both. The sum of the squares of the degrees of vertices is \(\displaystyle n^2-n\) where \(\displaystyle n\) is the number of vertices. What is the length of the shortest possible circuit in the graph?
Suggested by B. Montágh, Memphis
(5 pont)
Deadline expired on December 10, 2009.
Sorry, the solution is available only in Hungarian. Google translation
Megoldás. A legrövidebb kör hossza legfeljebb 5. Tegyük fel ugyanis, hogy a legrövidebb kör hossza \(\displaystyle k\ge 6\), és legyen \(\displaystyle C=v_1v_2\ldots v_kv_1\) egy ilyen kör. Ekkor a gráf élei között \(\displaystyle v_1v_3, v_1v_4\) és \(\displaystyle v_2v_4\) nem szerepelhet. A feltétel miatt a \(\displaystyle v_1,v_4\) csúcsoknak kell legyen egy \(\displaystyle v\) közös szomszédjuk, de az nem lehet sem \(\displaystyle v_2\), sem pedig \(\displaystyle v_3\), tehát \(\displaystyle v_1v_2v_3v_4vv_1\) egy \(\displaystyle k\)-nál rövidebb kör a gráfban, ami ellentmondás. Az alábbiakban megmutatjuk, hogy a gráf sem háromszöget, sem négyszöget nem tartalmazhat, vagyis a legrövidebb kör hossza csakis 5 lehet.
Tekintsük az összes olyan \(\displaystyle (u,v,w)\) rendezett hármast, ahol \(\displaystyle u,v,w\) a gráf olyan páronként különböző csúcsai, melyekre \(\displaystyle uv\) és \(\displaystyle vw\) egyaránt élei a gráfnak, \(\displaystyle uw\) azonban nem. Ezeknek a száma legyen \(\displaystyle K\). A gráf csúcsait jelölje \(\displaystyle v_1,v_2,\ldots,v_n\), a \(\displaystyle v_i\) csúcs fokszámát pedig \(\displaystyle d_i\). Ekkor a feltétel szerint
\(\displaystyle \sum_{i=1}^nd_i^2=n^2-n.\)
Vizsgáljuk meg először azt, hogy a \(\displaystyle v_i\) csúcs hány ilyen rendezett hármasban szerepelhet, mint a középső \(\displaystyle v\) csúcs. Mivel ekkor \(\displaystyle u\) és \(\displaystyle w\) a \(\displaystyle v_i\) csúcs különböző szomszédai, az ilyen hármasok száma legfeljebb \(\displaystyle d_i(d_i-1)\), a becslés pedig éppen akkor pontos, ha \(\displaystyle v_i\) szomszédai közül semelyik kettő nincs éllel összekötve. Ennek alapján azt kapjuk, hogy
\(\displaystyle K\le \sum_{i=1}^n(d_i^2-d_i)=(n^2-n)-\sum_{i=1}^nd_i,\)
ahol egyenlőség pontosan akkor teljesül, ha a gráf nem tartalmaz háromszöget.
Most nézzük meg azt, hogy a \(\displaystyle v_i\) csúcs hány rendezett hármasban szerepel első \(\displaystyle u\) elemként. Ekkor a \(\displaystyle w\) elem csak azon \(\displaystyle n-1-d_i\) csúcs közül kerülhet ki, melyek \(\displaystyle v_i\)-vel nem szomszédosak, másrészt viszont minden ilyen \(\displaystyle w\) csúcshoz találhatunk alkalmas \(\displaystyle v\) elemet is \(\displaystyle u=v_i\) szomszédai közül, hiszen bármely két éllel össze nem kötött csúcsnak van közös szomszédja. Ezért az ilyen hármasok száma legalább \(\displaystyle n-1-d_i\), és pontosan akkor nem több, ha bármely olyan \(\displaystyle w\) csúcsra, mely \(\displaystyle v_i\)-vel nem szomszédos, az \(\displaystyle w\) és \(\displaystyle v_i\) csúcsoknak pontosan egy közös szomszédja van. Ennek alapján azt kapjuk, hogy
\(\displaystyle K\ge \sum_{i=1}^n(n-1-d_i)=(n^2-n)- \sum_{i=1}^nd_i,\)
ahol egyenlőség pontosan akkor teljesül, ha bármely két éllel össze nem kötött csúcsnak csak egy közös szomszédja van, vagyis ha a gráf nem tartalmaz négy hosszúságú kört.
A két megállapítást összevetve látható, hogy szükségképpen
\(\displaystyle K=(n^2-n)- \sum_{i=1}^nd_i,\)
a gráf pedig sem háromszöget, sem négyszöget nem tartalmazhat. Ezzel korábbi állításunkat beláttuk, a gráfban a legrövidebb kör hossza 5. Ilyen gráfra legegyszerűbb példa az ötszög gráf, de könnyen ellenőrizhetjük, hogy az ún. Petersen-gráf is kielégíti a feladat feltételeit.
Statistics:
7 students sent a solution. 5 points: Ágoston Tamás, Damásdi Gábor, Éles András, Mester Márton, Mészáros András, Strenner Péter. 4 points: Perjési Gábor.
Problems in Mathematics of KöMaL, November 2009