Feladat: 4.15.
* Egy egyszerű gráfról azt tudjuk, hogy bármely három pontja között páros sok él fut. Mit mondhatunk még erről a gráfról? Adjunk szükséges és elégséges feltételt arra, hogy egy gráfnak meglegyen ez a tulajdonsága!
Megoldás: 4.15
Tegyük fel, hogy van benne egy
(x,y) él. Minden további pontra igaz, hogy
x és
y közül pontosan az egyikkel van összekötve. Osszuk őket eszerint két osztályba, az elsőben vannak az
y-nal összekötött (és
x-szel össze nem kötött) pontok, a másodikban az
x-szel összekötött (és
y-nal össze nem-kötött) pontok. Vegyünk két,
y-nal egy osztályban levő pontot és
y-t. E három pont között nem futhat él, mert
y-nal egyikük sincs összekötve. Tehát az egy osztályban levő pontok között nem fut él. Másrészt vegyünk két, különböző osztályba tartozó pontot és
x-et.
x a két másik pont közül pontosan az egyikkel van összekötve, tehát a másik kettő össze van kötve egymással.
Azt kaptuk, hogy a gráf egy teljes páros gráf. Nyilvánvaló, hogy minden teljes páros gráfra teljesül is a feladat feltétele.