Problem A. 508. (April 2010)
A. 508. An induced subgraph \(\displaystyle S\) of the graph \(\displaystyle G\) is called ``dominant'' if every vertex of \(\displaystyle G\), outside \(\displaystyle S\), has a neighbor in \(\displaystyle S\). Does there exist such a graph which has an even number of dominant subgraphs?
Proposed by: László Miklós Lovász, Budapest
(5 pont)
Deadline expired on May 10, 2010.
Sorry, the solution is available only in Hungarian. Google translation
Megoldásvázlat. Legyen a gráf G=(V,E), és definiáljunk egy új gráfot. Az új gráf csúcsai legyenek V nemüres részhalmazai. Két részhalmazt akkor kössünk össze, ha diszjunktak, és nem megy él az egyik halmazból a másikba.
Nézzük, mennyi lehet egy H
V részhalmaznak a foka az új gráfban. Ha egy H domináns, akkor minden P pont vagy benne van H-ban, vagy megy él P-ből H-ba. Ez azt jelenti, hogy ha V egy nemüres részhalmaza diszjunkt H-tól, akkor megy belőle él H-ba, tehát semmiképpen sincs összekötve H-val az új gráfban, vagyis egy domináns részhalmaz foka nulla.
Most tegyük fel, hogy H nem domináns. Álljon H1 azokból a pontokból, amelyek nincsenek H-ban, és nem is megy belőlük él H-ba. Ez tehát nem üres. Egy H2V akkor és csak akkor lesz H-val összekötve, ha H1-nek részhalmaza. Mivel az üres halmaz nincs a csúcsok között, ha H1-ben k pont van, akkor H-nak 2k-1 szomszédja van, ami páratlan, mivel k>0.
Tehát pontosan a nem domináns részhalmazoknak páratlan a foka az új gráfban, így páros sok van belőlük. Az üres halmaz nyilvan sosem domináns, így összesen páratlan sok nemdomináns halmaz van, de összesen páros sok részhalmaz van, tehát páratlan sok domináns részhalmaz van.
Statistics:
6 students sent a solution. 5 points: Backhausz Tibor, Bodor Bertalan, Nagy 235 János, Nagy 648 Donát. 1 point: 2 students.
Problems in Mathematics of KöMaL, April 2010