Matematické Fórum

No predne to je neporadne napsene. Podle slovika "pak" bych cekal implikaci, "jestlize ....., pak ...." ale to "jestlize" tam nevidim.

Negace implikace je konjukce, takze v tom znegovanem vyroku by mela (krom jineho) figurovat spojka "a".

↑ Kondr:

zadání je správně, to že v úplném grafu K4 mají všechny vrcholy stupeň 3 je jasné a odporuje to zadání, proto se má tato věta vyvrátit, jelikož zjevně není pravdivá. Ale jak to správně formulovat?
Šel jsem na to pomocí varianty odebrání hrany mezi dvěma vrcholy xy a z definice úplného grafu je jasné, že vrchol x je spojen hranou s jiným vrcholem z, se kterým je současně spojen hranou také vrchol y. To znamená že hrana xy není mostem.
Ale není správná matematická formulace, pro důkaz sporem...

↑ maly_kaja_hajnejch-Lazov:
Takže tedy přesné znění zadání:
Rozhodněte zda platí tvrzení (vyvraťte sporem)
v G neexistuje most -> G má všechny vrcholy sudého stupně.

moje verze důkazu:
Nechť existuje úplný graf K4, kde každý vrchol je spojen hranou se všemi ostatními vrcholy. Všechny vrcholy jsou tedy stupně lichého - 3. Pro spor předpokládejme, že existuje hrana e=(v1,v2) a tato hrana tvoří most v grafu K. To znamená, že K-e musí mít více komponent (o jednu) než původní graf K. Vrcholy v1 a v2 potom leží v různých komponentách grafu K. Z definice úplného grafu K4 však vyplývá, že vrcholy v1 a v2 jsou spojeny hranou s vrcholy v3 a v4. To znamená, že v grafu K-e existuje cesta P=(v1,v3,v2), což je spor s tím, že vrcholy v1 a v2 leží po odebrání hrany e=(v1,v2) v různých komponentách.

ale není to správně.... prý pokud se má vyvrátit tvrzení, tak to znamená dokázat pravdivost negace tohoto tvrzení. Nejprve je tedy nutné větu znegovat a pak ukázat nejlépe na obrázku, že takový graf skutečně existuje.

tak tedy negace věty:
v G neexistuje most a G má všechny vrcholy lichého stupně.
potom takový graf namalovat - namalovat úplný graf například K4

je to správný důkaz?