graph - n 個の頂点を持つ無向グラフが常に接続されるために必要なエッジの最小数はいくつですか?

Question

n 個の頂点を持つ無向グラフを接続するには、n - 1 個の辺が必要であることを知っています。ただし、私の質問は、常に接続できるエッジの最小数はいくつですか。たとえば、n 個の頂点と n + 2 個のエッジを持つグラフは常に接続されている必要がありますか? そうでない場合、常に接続するために必要なエッジの数はいくつですか?

Answer 1

頂点グラフが接続されていないエッジの最大数はn-2 です。 3 つの頂点を持つグラフの場合、それを接続するには少なくとも 2 つのエッジが必要です。これはn-1、それよりも 1 つのエッジが少ないため、グラフが切断される最大のエッジが得られます。

n 個の頂点とn + 2エッジを持つグラフは常に接続されている必要があります: 自己ループが許可されているかどうかによって異なります。 4 つの頂点と 6 つのエッジの場合、可能でも不可能でもあります。