グラフ理論の問題

各頂点の次数を求める。 頂点 $v$ の次数は、「$12$ 以下の $v$ の約数のうち $v$ 以外のものの個数」と「$12$ 以下の $v$ の倍数のうち $v$ 以外のものの個数」の和である。

• $\mathrm{deg}1=11$（$1$ は他のすべての頂点を割り切る）
• $\mathrm{deg}2=1+5=6$（約数は $1$、倍数は $4,6,8,10,12$）
• $\mathrm{deg}3=1+3=4$（約数は $1$、倍数は $6,9,12$）
• $\mathrm{deg}4=2+2=4$（約数は $1,2$、倍数は $8,12$）
• $\mathrm{deg}5=1+1=2$（約数は $1$、倍数は $10$）
• $\mathrm{deg}6=3+1=4$（約数は $1,2,3$、倍数は $12$）
• $\mathrm{deg}7=1$（約数は $1$）
• $\mathrm{deg}8=3$（約数は $1,2,4$）
• $\mathrm{deg}9=2$（約数は $1,3$）
• $\mathrm{deg}10=3$（約数は $1,2,5$）
• $\mathrm{deg}11=1$（約数は $1$）
• $\mathrm{deg}12=5$（約数は $1,2,3,4,6$）

次数の和は $46$ なので、辺は $23$ 本ある。次数が奇数の頂点は $1,7,8,10,11,12$ の $6$ 個である。また、頂点 $1$ が他のすべての頂点と隣接しているので、$G$ は連結である。

下界。 1 本の道について、その道の辺だけを数えた各頂点の次数を考える。始点と終点が異なる道では、始点と終点だけが奇数になり、ほかの頂点はすべて偶数になる。閉じた道では、すべての頂点で偶数になる。辺を $k$ 本の道に分けると、$G$ での各頂点の次数は各道での次数の和になる。したがって、$G$ で次数が奇数の頂点は、いずれかの道の端点でなければならない。$k$ 本の道の端点は高々 $2k$ 個なので、$2k\ge 6$、すなわち $k\ge 3$ である。

3 本で実現できること。 奇数次数の 6 頂点を 3 組に分け、各組を結ぶ新しい辺を 1 本ずつ加える（すでにある辺と平行になってもよい）。こうして得られる多重グラフ $G^{\prime }$ は連結で、すべての頂点の次数が偶数である。よってオイラーの定理により、$G^{\prime }$ にはオイラー閉路がある。このオイラー閉路から加えた 3 本の辺を取り除くと、閉路は 3 つの部分に切れる。それぞれは $G$ の辺だけからなり、同じ辺を 2 度通らない道である。これで $G$ の辺が 3 本の道に分けられた。

以上より、求める最小値は $3$ である。

G は 1 を通じて連結（1 はすべての頂点と隣接）で、辺を持たない頂点はない。各頂点の次数を数える。

• 1: 11（奇）
• 2: 倍数 4,6,8,10,12 の 5 個と約数 1 の 1 個で 6
• 3: 倍数 6,9,12 と約数 1 で 4
• 4: 倍数 8,12 と約数 1,2 で 4
• 5: 倍数 10 と約数 1 で 2
• 6: 倍数 12 と約数 1,2,3 で 4
• 7: 約数 1 のみで 1（奇）
• 8: 約数 1,2,4 で 3（奇）
• 9: 約数 1,3 で 2
• 10: 約数 1,2,5 で 3（奇）
• 11: 約数 1 のみで 1（奇）
• 12: 約数 1,2,3,4,6 で 5（奇）

次数の総和は 11+6+4+4+2+4+1+3+2+3+1+5=46 で、辺数は 23。これは握手補題と合う。

奇点は 1,7,8,10,11,12 の 6 個。1 本の道（トレイル）は端点が奇点になるので、1 本あたり奇点を高々 2 個しか端点にできない。したがって少なくとも 6/2=3 本は必要。

連結で奇点が 2k 個のグラフは、辺を k 本の辺素なトレイルに分割できることが知られている。実際、奇点を 3 組に分けて、それぞれの組に新しい辺（仮想辺）を加えると全頂点の次数が偶数になり、連結なのでオイラー回路が存在する。この回路から仮想辺 3 本を除くと 3 本のトレイルになる。

よって最小値は 3。