Matematické Fórum

Zadání:
Dokažte, že graf na n vrcholech s c komponentami, má alespoň (n-c) hran, kde n>=c a zároveň n, c jsou přirozená.

Logika příkladu:
Mám c komponent. Každá JEDNA z nich tvoří souvislý podgraf, protože kdyby nebyl souvislý, čili by neplatilo, že pro každé dva vrcholy u, v existuje cesta z u do v, pak by se nejednalo o JEDNU komponentu, nýbrž o dvě. A protože libovolně vybraná komponenta je souvislá, musí mít pro jejích q vrcholů alespoň (q-1) hran, což je ekvivalentní tvrzení k pro jejích q vrcholů má alespoň (q-d) hran, kde d je počet komponent podgraf, která je jedna. Kdyby nebyla jedna, opět bychom se dostali do druhé věty o jedné komponentě.

Tuhle úvahu pak můžeme převést na celou množinu n vrcholů a c komponent, kde n získáme jako součet vrcholů všech podgrafů a c je počet komponent.

Jak bych měl tuhle úvahu převést na důkaz, resp. stačila by tato úvaha jako důkaz?

Díky