Feladat: 10.8.
** Mutassuk meg, hogy minden gráf csúcsai két részre vághatók úgy, hogy a pontoknak a saját osztályukban páros sok szomszédjuk van. (Vagyis a két osztály által feszített két részgráfban minden pont foka páros.)
Megoldás: 10.8
A gráf pontjai szerinti teljes indukciót alkalmazunk. Ha minden pont foka páros, akkor nincs mit bizonyítanunk.
Ellenkező esetben van egy páratlan fokú
x pont. Legyen
x szomszédainak halmaz a
S, és a többi pont halmaza
T. Vegyük az
S által feszített részgráf komplementerét és vegyük ehhez hozzá az
ST és a
TT éleket.
A kapott
G' gráfra alkalmazzuk az indukciós feltételt:
S is,
T is két
részre bomlik -
S=S'∪S" és
T=T'∪T" - úgy, hogy az
S'∪T' és az
S"∪T" által
G'-ben feszített részgráfokban minden pont foka páros.
S' és
S" közül az egyik páratlan, a másik páros sok pontból áll, mondjuk
S' áll páratlan sokból és
S" páros sokból. Cserélljük ost vissza
S'-ben és
S"-ben az éleket az eredeti élekre és tegyük hozzá
x-et
S"-höz. Ekkor
S'-ben minden pont fok paritása megmarad(!) és
S"-ben megfordul, de miután hozzávettük
x-et, amivel
S" minden pontja össze van kötve, ezért itt is minden pont foka páros marad. Végül
x foka is páros, hiszen
S" minden pontjával össze van kötve és
S" pontszáma páros.
Ezzel a bizonyítást befejeztük.