グラフ理論に関する次の記述のうち，最も適切なものはどれか。
① 完全 2 部グラフは，すべての頂点同士が辺で繋がっている。
② 距離を重みとする重み付きグラフでは，ある頂点から別の頂点への移動に要する重みは，どの順路でも常に同じである。
③ 頂点から出た辺が同じ頂点に戻るループのみである場合，その頂点は孤立点である。
④ 3 つの頂点及び 3 つの辺で構成される単純閉路グラフならば，いずれの頂点でも次数は2である。
⑤ 無向完全グラフでは，頂点の数を n としたとき，辺の数は 2n となる。
答え
④
解説
① 完全 2 部グラフは，すべての頂点同士が辺で繋がっている。
完全 2 部グラフは同一の集合の頂点同士が繋がっている必要はないため，不適切です。
② 距離を重みとする重み付きグラフでは，ある頂点から別の頂点への移動に要する重みは，どの順路でも常に同じである。
順路によって重みが異なるため，不適切です。
③ 頂点から出た辺が同じ頂点に戻るループのみである場合，その頂点は孤立点である。
ループがあるということは，次数は 2 になるため，不適切です。
④ 3 つの頂点及び 3 つの辺で構成される単純閉路グラフならば，いずれの頂点でも次数は2である。
適切です。各頂点から他の 2 頂点に辺が引かれる三角形になります。
⑤ 無向完全グラフでは，頂点の数を n としたとき，辺の数は 2n となる。
辺の数は，1 / 2n(n-1) になります。