\[
\newcommand\l{\left}
\newcommand\r{\right}
\newcommand\cmt[1]{\class{Cmt}{\mbox{#1}}}
\newcommand\b[1]{\class{Bold}{\mathrm{#1}}}
\newcommand\bx{\b{x}}
\newcommand\bw{\b{w}}
\newcommand\bv{\b{v}}
\newcommand\bu{\b{u}}
\newcommand\T{\mathrm T}
\]
あるツリーがN個のメッセージを送ったあと保留メッセージがなくなったとする。
このときのメッセージ列を
\[
M_1,M_2,\cdots,M_N
\]
とする。このツリーの任意のノード p に葉ノード o を追加する。
新しくできたツリーのメッセージ列は
\[
\begin{align}
&メッセージ列の先頭にノード\ o\ \to\ ノード\ p\ のメッセージ\ \color{red}{M_0}\ を追加する \tag{1} \\
&メッセージ列の末尾にノード\ p\ \to\ ノード\ o\ のメッセージ\ \color{red}{M_{N+1}}\ を追加する。 \tag{2} \\
&メッセージ列のうちノード\ p から\ o\ 以外の隣接ノードへの送信メッセージ\color{#0099ff}{M_{p1},\cdots}を \tag{3}\\
&\ \color{red}{M_0}\ を含むように変える
\end{align}
\]
という手順で得ることができる。得られたメッセージ列は
\[
\color{red}{M_0},M_1,M_2,\cdots,\color{#0099ff}{M_{p1}},\cdots,M_N,\color{red}{M_{N+1}}
\]
となり、これを送信したあと保留メッセージは残らない。\((\because 視察により)\)
よって、有限個のメッセージ送信で保留メッセージがなくなるツリーに葉ノードを1つ付け加えたものは、有限個のメッセージで保留メッセージがなくなる。と言える。
次に、ノード1つからなるツリーは保留メッセージを持たない。
また、すべてのツリーはノード1つから始めて1つづつ葉ノードを追加していくことで作ることができる。\((\because 視察により)\)
以上よりすべてのツリーは有限個のメッセージを送信したあと保留メッセージがなくなる。と言える。