Problem A. 606. (January 2014)

A. 606. Prove that for every simple graph G with n vertices there exist some simple graphs S₁, ..., S_k with the following properties:

(a) every S_i is a complete bipartite graph;

(b) every edge of G is contained by an odd number of graphs S_i;

(c) every edge of the complement of G is contained by an even number of graphs S_i;

(d) .

(5 pont)

Deadline expired on February 10, 2014.

Sorry, the solution is available only in Hungarian. Google translation

Megoldásvázlat. Legyen G csúcshalmaza V. A megoldáshoz csak olyan gráfokat fogunk használni, amelyek csúcsai a V halmazból kerülnek ki. Az ilyen gráfokat azonosítani fogjuk az éleik halmazával; minden egyes gráfnak megfelel tehát egy V-beli, különböző elemekből álló rendezetlen párokból álló halmaz. Tetszőleges A,BV diszjunkt halmazokra (A×B)-vel fogjuk jelölni azt a teljes gráfot, amelynek két csúcshalmaza A, illetve B. (Ez nem azonos a halmazelméletből ismert Descartes-szorzattal.)

Nevezzük két gráf, G₁ és G₂ szimmetrikus differenciájának azt a gráfot, amit úgy kapunk, hogy vesszük azokat az éleket, amik G₁ és G₂ közül pontosan az egyikben szerepelnek. A szimmetrikus differenciát jelöljük -vel. A művelet kommutatív és asszociatív, így beszélhetünk több gráf szimmetrikus differenciájáról, a sorrend és zárójelezés megadása nélkül is.

Jelöljük f(n)-nel a legkisebb olyan nemnegatív egész számot, amire igaz, hogy tetszőleges n pontú gráf előáll legfeljebb f(n) teljes gráf szimmetrikus differenciájájaként. A feladat megoldásához azt kell igazolnunk, hogy . n szerinti indukcióval bizonyítunk. Könyen ellenőrizhetjük, hogy f(0)=f(1)=0, f(2)=1 és f(3)=2, ezért az állítás teljesül n3 esetén. Tegyük fel, hogy n4, és az állítás igaz minden kisebb értékre.

1. eset: A gráfban van egy a izolált pont. Ekkor a G\{a} gráf előáll legfeljebb f(n-1) teljes páros gráf összegeként.

2. eset: A gráfban van két szomszédos pont, a és b, amiknek nincs közös szomszédja. Legyen az a csúcs b-től különböző szomszédainak halmaza A, a b csúcs a-tól különböző szomszédainak halmaza pedig B. Az S=({a}B)×({b}A) gráfban szerepel az összes a-ból vagy b-ből induló él.

Vizsgáljuk most a gráfot. Ennek a gráfnak a és b is izolált pontja, így G' előállításához biztosan elég f(n-2) teljes gráf. Mivel , az S gráfot hozzávéve ez egy összesen legfeljebb f(n-2)+1 gráfból álló előállítás.

3. eset: A gráfban van három pont, a, b és c, amik egy háromszöget alkotnak, de nincs közös szomszédjuk. Legyen a, b és c további szomszédainak halmaza rendre A, B és C. A feltevésünk szerint ABC=Ø.

Legyen

Az gráf tartalmazza az összes a,b,c-ből induló élt.

A gráfban a, b és c is izolált csúcs, ezért gráfot előállíthatjuk összesen f(n-3)+2 teljes páros gráf szimmetrikus differenciájaként.

4. eset: A gráfban van négy pont, a, b, c és d, amik páronként szomszédosak. Az összes a-ból, b-ből, c-ből vagy d-ből induló élt előállítjuk három teljes páros gráf szimmetrikus differenciájaként. A három gráfot úgy konstruáljuk, hogy először előállítjuk az {a,b,c,d} csúcsú teljes gráfot: , majd ezekhez hozzávesszük a G gráf bizonyos csúcsait.

A további csúcsokat összesen 16 halmazra bonthatjuk aszerint, hogy a,b,c,d közül melyekkel szomszédosak. Ezeket a halmazokat V_Ø-zal, V_a-val, V_abc-vel stb. fogjuk jelölni; az indexekben az a,b,c,d csúcsok közül azokat soroljuk fel, amelyek szomszédok. Tehát például V_abc azoknak az a,b,c,d-től különböző csúcsoknak a halmaza, amelyek szomszédosak a,b,c-vel, de nem somszédosak d-vel.

Most megadjuk a három teljes gráfunkat; legyen

Ezzel a választással a gráfban a, b, c és d is izolált pont, így előállítható legfeljebb f(n-4) teljes gráf szimmetrikus differenciájaként; Ezekhez hozzávéve az S₁,S₂,S₃ gráfokat, a G gráfot f(n-4)+3 teljes gráffal állítjuk elő.

A négy eset közül legalább az egyik bekövetkezik, így

Statistics:

4 students sent a solution.
5 points:	Ágoston Péter, Maga Balázs.
4 points:	Simon 047 Péter.
0 point:	1 student.

Problems in Mathematics of KöMaL, January 2014