グラフ理論の問題

各頂点の次数. 辺の一覧から数えると
$$\mathrm{deg}1=3,\mathrm{deg}2=3,\mathrm{deg}3=3,\mathrm{deg}4=3,\mathrm{deg}5=4,\mathrm{deg}6=4,\mathrm{deg}7=3,\mathrm{deg}8=3$$
である（合計 $26=2\times 13$ で、握手補題と合う）。次数が奇数の頂点は $1,2,3,4,7,8$ の $6$ 個である。

下からの評価. $1$ 本の小道について、その小道が通る辺のうち頂点 $v$ に接する辺の本数を考える。$v$ が小道の途中で通過されるたびに $2$ 本ずつ使われるので、$v$ が小道の端点（始点か終点のどちらか一方だけ）であるときに限り、その本数は奇数になる。したがって、$1$ 本の小道で「接する辺を奇数本使う頂点」は高々 $2$ 個である。

辺を $k$ 本の小道に分けたとき、各頂点 $v$ で $\mathrm{deg}v$ はそれぞれの小道で使われる本数の和である。$\mathrm{deg}v$ が奇数なら、少なくとも $1$ 本の小道で $v$ に接する辺を奇数本使っている。奇数次の頂点は $6$ 個あり、$1$ 本の小道で対応できるのは高々 $2$ 個なので
$$2k\ge 6,\text{すなわち}k\ge 3$$
である。

3 本で分けられること. 次の $3$ 本の小道をとる。
- $T_1$: $1\to 2\to 3\to 1\to 4$（辺 $\{1,2\},\{2,3\},\{1,3\},\{1,4\}$）
- $T_2$: $2\to 5\to 4\to 7\to 6\to 3$（辺 $\{2,5\},\{4,5\},\{4,7\},\{6,7\},\{3,6\}$）
- $T_3$: $7\to 8\to 5\to 6\to 8$（辺 $\{7,8\},\{5,8\},\{5,6\},\{6,8\}$）

どれも同じ辺を $2$ 度通らず、合わせて $4+5+4=13$ 本の辺をちょうど $1$ 回ずつ含む。

よって必要な小道の本数の最小値は $3$ である。（一般に、奇数次の頂点を $2k$ 個（$k\ge 1$）もつ連結グラフの辺は、ちょうど $k$ 本の小道に分けられる。）

各頂点の次数を求める。$\mathrm{deg}1=3$（2,3,4）、$\mathrm{deg}2=3$（1,3,5）、$\mathrm{deg}3=3$（1,2,6）、$\mathrm{deg}4=3$（1,5,7）、$\mathrm{deg}5=4$（2,4,6,8）、$\mathrm{deg}6=4$（3,5,7,8）、$\mathrm{deg}7=3$（4,6,8）、$\mathrm{deg}8=3$（5,6,7）。次数の和は $26=2\times 13$ で辺数と合う。

奇数次数の頂点は $1,2,3,4,7,8$ の 6 個。$G$ は連結である（1-2-3-6-5-4-7-8 が全頂点を通る）。

連結グラフで奇数次数の頂点が $2k$ 個（$k\ge 1$）のとき、辺をすべて使う小道への分割に必要な最小本数は $k$ である。
下界: 小道 1 本は端点が 2 つで、奇数次数の頂点はそれぞれ少なくとも 1 本の小道の端点でなければならない（途中で通過するたびに次数を 2 消費するため）。1 本の小道の端点は高々 2 個なので、6 個を覆うには少なくとも 3 本必要。
上界: 奇数次数頂点を 3 組にペアにして、補助辺を加えると全頂点が偶数次数の連結グラフとなりオイラー閉路が存在する。補助辺 3 本で閉路を切ると 3 本の小道に分かれる。

具体例: 小道 1: 1-2-3-1-4-5-2 （辺 12,23,31,14,45,52）→ 端点 1 と 2 ではなく、1 から始まり 2 で終わる。小道 2: 3-6-5-6 は同じ辺を重ねるので不可。そこで構成を取り直す。小道 A: 1-4-5-2-1-3（辺 14,45,52,21,13）、端点 1,3。小道 B: 2-3-6-5-8-6-7-4（辺 23,36,65,58,86,67,74）、端点 2,4。小道 C: 7-8（辺 78）。これで 5+7+1=13 本の辺をちょうど 1 回ずつ使う。小道 A の端点は 1 と 3、B は 2 と 4、C は 7 と 8 で、奇数頂点 6 個を 1 つずつ割り当てている。

よって最小値は 3。