Gráfelmélet. Hogyan igazoljam, hogy véges gráfban a komponensek számának, és az élek számának az összege nem kisebb, mint a csúcsszám?

Nézzük csak az egyik komponenst (vagyis egy összefüggő gráfot).

Építsük fel a gráfot úgy, hogy vesszük valamelyik pontját, majd sorban hozzáadunk egy olyan élet (plusz az élhez tartozó csúcsokat), aminek egyik csúcsa már az épülő gráfnak része. Mivel a gráf összefüggő, ezért így végül az összes élet (és csúcsot) hozzáadjuk.

Az első pont hozzáadásakor a komponensek (1) és élek számának (0) összege megegyezik a csúcsszámmal (1):

k+e=c

Aztán egy él hozzáadásakor ha az él másik csúcsa most kerül be a gráfba, akkor k+e és c is eggyel nő.

Ha a másik csúcs már része volt az épülő gráfnak, akkor k+e nő csak, k+e>c lesz.

Így az összefüggő gráfra igaz az összefüggés.

Ha több komponensű a gráf, mindegyik komponenssel elvégezhetjük ezt a gráfépítést, az egyenlőtlenség ugyanúgy alakul.