馬杉：無向グラフの彩色？
宿田：任意の二頂点間をどの色でも辿れる
渡辺：どのairlineも $n-1$ 本のairwayを持つ
宿田：これあと構成するだけ？
渡辺：$n/2$ で抑えられたね
馬杉：帰納法とか使えないの？
宿田：$n=6$ 作れた、もうなんか出来てそう (todo：図を追加)
馬杉：直接作った方が早いか
宿田：偶数、同様に出来ます…
馬杉：奇数も出来るか
宿田：偶数に $1$ 頂点足せば (※編注：ウニグラフを追加)

• 最大値・最小値を求める問題は、基本的に「構成による評価」と「考察による評価」の2フェーズ

都市を頂点として航空路線を辺とした無向グラフを考える. $m$頂点からなる連結な無向グラフは $(m-1)$ 本以上の辺をもつことから, すべての航空会社は $(n-1)$ 本以上の辺をもつ. 辺の総数は高々 $n(n-1)/2$ 本だから航空会社の数は $n/2$ 以下である.

$[n/2]$ の航空会社について条件をみたす辺の割り当て方が存在することを示す. 以下, $n$ 個の頂点を $1,2,\cdots n$ とし, 番号に関する加法減法は $modn$ で考える. $k$ を正の整数とする. $n=2k$ のとき, $i=1,2,\cdots k$ , $j=1,2,\dots 2k-1$ に対し, $i$ 番目の航空会社の $j$ 番目の辺に, $j$ が奇数のときは, $i-\frac{j-1}{2}$ と $i+\frac{j+1}{2}$ を結ぶ辺を, $j$ が偶数のときは, $i-(j/2)$ と $i+(j/2)$ を結ぶ辺を割り当てる. これが条件をみたすことは確認できる. $n=2k+1$ のとき, 頂点 $0,1,\cdots 2k-1$ の間の辺を $n=2k$ の場合と同様に $k$ 個の航空会社に割り当て, これに加えて $i=1,2,\cdots k$ に対して, $i$ 番目の航空会社に $2k$ と $i$ を結ぶ辺を割り当てればよい. 以上より $[n/2]$ の航空会社について条件をみたす辺の割り当て方が存在し, 求める最大値は $[n/2]$ である.