Matematické Fórum

2-souvislý=oddělám jeden vrchol a je stále souvislý. To ale každý Hamiltonovský graf splní, protože má jako podgraf hamiltonovskou kružnici, která po odebrání jednoho vrcholu bude stále spojovat všecchny zbylé.

Stejně tak musí být hranově 2 souvislý - pokud odebraná hrana neleží na Hamiltonovské kružnici, graf zůstanene spojen touto kružnicí. Pokud odebraná hrana na kružnici leží, z kružnice zbude n-1 hran, které stále spojují všech n vrcholů.

Co se týče protipříkladu opačné implikace, napadá mě tento:
       o

x     x    x

      o
Přičemž každé x je spojené hranou s každým o.  V každém vrcholu hamiltonovského grafu končí dvě z hran hamiltonovské kružnice -- v tomto grafu by to znamenalo, že Hamiltonovská kružnice obsahuje všechny jeho hrany, což je spor.
Snadno nahlédneme, že graf je vrcholově i hranově 2-souvislý.

↑ Saturday:
krome hran ktere tvori kruznici tam muzou byt i nejake navic

jjjjj díky:)