Se un grafico G (V, E) è collegato $ | E | \ Geq | V | -1 $

Question

Se è collegato un grafico G (V, E), il numero di bordi è almeno il numero di vertici-1. È abbastanza evidente se ci pensi, ma come lo dimostrezzo formalmente?

Answer 1

Immagina un processo in cui si inizia con il grafico vuoto e aggiungi i bordi uno per uno.Tieni traccia del numero di componenti collegati.All'inizio, ci sono $ | v | $ componenti collegati.Ogni bordo si aggiunge sia appartenente all'interno di un componente collegato o si unisce due componenti collegati e, in ogni caso, il numero di componenti collegati diminuisce al massimo 1. quindi dopo aver aggiunto $ | E |$ bordi, il numero di componenti collegati è almeno $ | V |- | e | $ .Se il grafico è collegato, $ | V |- | e |\ Leq 1 $ e così $ | e |\ Geq | V |- 1 $ .