\(N>2\) とします.

公式解説 の \(K\) （次数が 2 以上の頂点の個数）を固定して考えます.

そのような \(X\) の個数は \(\binom{N}{K} \binom{N-3}{N-2-K}\) です.

したがって答えは

\[ \sum_{K=1}^{N-2} (K+1) \binom{N}{K} \binom{N-3}{N-2-K} = \sum_{K=1}^{N-2} \binom{N}{K} \binom{N-3}{N-2-K} + \sum_{K=1}^{N-2} K\binom{N}{K} \binom{N-3}{N-2-K} \]

となります.

ここで,

\[\binom{N}{K} = [x^K] (1+x)^N\]

が成り立つので,

\[ \begin{aligned} \sum_{K=1}^{N-2} \binom{N}{K} \binom{N-3}{N-2-K} &= [x^K] (1+x)^N \times [x^{N-2-K}](1+x)^{N-3} \\ &= [x^{N-2}](1+x)^{2N-3} \\ &= \binom{2N-3}{N-2} \end{aligned} \]

\[ \begin{aligned} \sum_{K=1}^{N-2} K \binom{N}{K} \binom{N-3}{N-2-K} &= [x^{K-1}] \dfrac{d}{dx}(1+x)^N \times [x^{N-2-K}](1+x)^{N-3} \\ &= [x^{K-1}]N(1+x)^{N-1} \times [x^{N-2-K}](1+x)^{N-3}\\ &= N[x^{N-3}](1+x)^{2N-4}\\ &= N\binom{2N-4}{N-3} \end{aligned} \]

したがって \(\binom{2N-3}{N-2} + N\binom{2N-4}{N-3}\) が答えとなります.