Segítene valaki kombinatorikából?

Nincs

Nincs

Van

Az első nagyon benézte.

De nem elég csak annyit mondani, hogy nincs, hanem valamire hivatkozni kell tudni hogy nincs.

A G1 gráf esetén ha kitöröljük az egyik megfelelő pontot, akkor a gráf két komponensre szétesik. Tudjuk, hogy ha egy gráf n csúcs törlésével n-nél több komponensre hullik szét, akkor nem lehet Hamilton-köre. Már pedig 1 cúscs törlésével 1-nél több komponens keletkezett, tehát nincs benne Hamilton-kör.

A G2 esetén a két "legalsó" csúcsot törölve 3 komponensre esik szét a gráf, és mivel 2<3, ezért a fentiek értelmében nincs a gráfban Hamilton-kör.

A G3 azért érdekes, mert akárhogyan töröljük a csúcsokat, nem fog soha több komponensre szétesni, mint ahány csúcsot törlünk, mégsem tartalmaz Hamilton-kört. Ennek a G3 gráfnak egyébként sok más fontos tulajdonsága is van, és még nevet is adtak neki: Petersen-gráf. Ennek bizonyítása megtalálható a linken:

[link]