Feladat: 4.24.
Két négypontú gráf minden hárompontú feszített részgráfja két élt tartalmaz. Következik-e ebből, hogy a két négypontú gráf izomorf?
 

Megoldás: 4.24
Legyen az egyik gráf egy hárompontú részgráfjának három pontja a,b,c és tegyük fel, hogy az (a,b) és (b,c) élek szerepelnek a gráfban, az (a,c) él nem. A másik gráf egy hárompontú részgráfja legyen a',b'c', ezek között az (a',b') és (b',c') élek be vannak húzva, az (a',c') nincs. A feltételből következik, hogy az a,c,d hárompontú részgráfban az (a,d) és (d,c) élek be vannak húzva, s ugyanígy a másik gráfban az (a',d') és (d',c') élek is be vannak húzva. Végül például az a,b,d hárompontú részgráfban be van húzva az (a,b) és (a,d) élek, tehát a (b,d) él nincs behúzva, ugyanígy a másik gráfban a (b',d') él nincs behúzva. Az a→a', b→b', c→c', d→d' leképezés tehát a két gráf közötti izomorfiát ad meg.