OMC174(C) - 公式解説の補足

　公式解説の $G$ について，各辺が結ぶ $2$ 頂点の偶奇は異なるから，$G$ は奇数の頂点の集合と偶数の頂点の集合をそれぞれ部集合に持つ二部グラフであることに注目する．上部に奇数の頂点を，下部に偶数の頂点を並べ，また辺で結ばれる頂点同士が近くなるように，奇数は $1,\, 3,\, \ldots,\, 99$，偶数は $100,\, 98,\, \ldots,\, 2$ の順に並べ，そして和 $103$ の辺が鉛直になるようにすれば，グラフの形をイメージしやすい．公式解説では，和が $103$ の頂点の組に対し，$1$ 組おきにひっくり返すことでさらに見やすくしているが，そのままでも十分であるから，ここではそうしよう．
　次に，公式解説の誘導部分グラフについて，頂点の数と辺の数が等しいことから，木では辺の数が足りない．よってどこかにサイクルができていて，$G$ の形状から $\Join$ の形を持たなければならないことが分かる．あとは $\Join$ を二つくっつけたもの${}+1$ 点とするか，$\Join$ に合計 $3$ 辺の木をつなげればよい．後者の場合について，$\Join$ の同じ側において $\Join$ に隣接する $2$ 点を両方選ぶことはできないことに注意すると $$\mathord\Join\!\mathord\vee\!\backslash \qquad \mathord\Join\!\mathord\vee\!| \qquad /\!\mathord\Join\!\mathord\vee \qquad /\!\mathord\Join\!\mathord\wedge$$ に大別され，これが公式解説の図 $2$ に対応している．公式解説では，これをそれぞれ数えているが，$\Join$ の位置ごとにまとめて数えても良い．$\Join$ が端から $1,\, 2,\, 3$ 番目，それ以外の場合について，それぞれ $6,\, 10,\, 15,\, 16$ 通りであることが分かり，これより $$2 \times (6 + 10 + 15) + 42 \times 16 = 734$$ 通り．したがって $\mathord\Join\!\mathord\Join + 1$ 点の場合を公式解説と同様に数え上げれば，その $4232$ 通りと上を合わせて，求める場合の数は $\bm{4966}$ 通り．