グラフG（v、e）が$ | e | \ GEQ | v | -1 $

Question

グラフG（v、e）が接続されている場合、エッジ数は少なくとも頂点 - 1の数である。 あなたがそれについて考えるならば、それはかなり明白ですが、正式にそれを証明するのですか？

Answer 1

空のグラフから始めて、エッジを1つずつ追加したプロセスを想像してください。接続されたコンポーネントの数を追跡してください。最初は、 $ | $ 接続されているコンポーネントです。追加した各エッジは、接続されているコンポーネント内に属しているか、2つの接続されたコンポーネントをマージするか、いずれにせよ、接続されているコンポーネントの数は最大で1で減少します。 $ | e |$ エッジ、接続されているコンポーネントの数は少なくとも $ | v | - | e | $ 。グラフが接続されている場合は、 $ | v | - | e |\ LEQ 1 $ 、そしてsp span class="math-container"> $ | e |\ GEQ | V | - 1 $ 。