Если график g (v, e) подключен $ | e | \ geq | v | -1 $

Question

Если график g (v, e) подключен, количество ребер, по меньшей мере, количество вершин - 1. Это довольно очевидно, если вы думаете об этом, но как я могу доказать это формально?

Answer 1

Представьте себе процесс, в котором вы начинаете с пустого графа, и добавьте края один за другим.Следите за количеством подключенных компонентов.В начале есть $ | V | $ подключенные компоненты.Каждый край, который вы добавляете, либо принадлежат внутри подключенного компонента, либо объединяет два подключенных компонента, и в любом случае количество подключенных компонентов уменьшается с помощью максимума 1. Следовательно, после добавления $ | E |$ ребра, количество подключенных компонентов, по меньшей мере, $ | V |- | E | $ .Если график подключен, $ | v |- | е |\ leq 1 $ , и поэтому $ | E |\ GEQ | V |- 1 $ .