Matematické Fórum

4 určite nie je pravda uvažuj hviezdu s ľubovoľnou hranou navyše je to súvislé má práve toľko hrán čo uzlov a kružnica to nie je
je rozdiel JE kružnice a MÁ kružnicu

↑ ajucha:

Ad 3: dokazuj zvlášť implikace
"G je strom -> každé dva vrcholy spojuje právě jedna cesta" (co by se stalo, kdyby některé dva vrcholy spojovaly alespoň dvě cesty? Nebo některé dva vrcholy nespojovala žádná cesta?) EDIT: Teď se dívám, žes tam k tomu už něco psala, to je správně, ale není to ještě všechno
a "každé dva vrcholy spojuje právě jedna cesta -> G je strom" (strom se většinou definuje jako souvislý graf bez kružnic - platí-li předpoklad, je graf souvislý? platí-li předpoklad, může vzniknout kružnice?)

Ad 1: Zkus si pro spor představit, že má graf alespoň dvě komponenty souvislosti, a odhadnout, jak takové komponenty musí být velké : ))

Ad 2: Zde lze postupovat třeba tak, že nejprve ukážeme, že má-li graf všechny vrcholy sudého (nenulového - kdyby některé vrcholy měly nulový stupeň, vůbec je nemusíme v grafu uvažovat, vzhledem k tomu, že chceme dokázat tvrzení o hranách grafu) stupně, pak tam určitě vždy najdeme alespoň jednu kružnici. No a pak stačí nahlédnout, jak bude vypadat graf po odebrání takové kružnice ; )).

Příště, prosím, dávej do jednoho tématu jeden příklad v souladu s pravidly fóra.