MathLabs

第3問

正の整数 nn に対し、nn 人がパーティーに参加する。各二人は知り合いであるか、そうでない。知り合いではないが参加者の中に共通の知人をもつ組の最大数を求めよ。
ステップ 4/6: 連結グラフの評価
前のステップ次のステップ
e(G)≥n−1e(G)\ge n-1
詳しい解説

上の連結グラフは少なくとも nn 頂点に対して少なくとも n−1n-1 辺をもつ.