グラフ$ G $があるとしましょう。そこから1つのエッジ（任意のエッジ）を選択します。そのようなスパニングツリーは常に存在しますか？
答えはイエスだと思います。何をしても、選択したエッジが含まれるように、いつでもそのようなスパニングツリーを作成できるからです。もちろん、より正式な証明です。
コメント
- あなたは'非公式の証拠すら書いていません：本質的に、あなたは'と言った"答えはイエスなので、答えはイエスだと思います。"
回答
最初のグラフ $ G $を接続する必要があります。そうでない場合は、スパニングツリーがまったくありません（ただし、各コンポーネントに同じ引数を適用すると、グラフには、選択したエッジを含むスパニングフォレストがあることが示されます）。
$ G =（V、E）$を接続グラフとし、 $ T $は任意のスパンサブツリーであり、$ e $を任意のedgein $ E $とします。 $ e $を含むスパニングツリーがあると主張しています。 $ e \ in T $の場合、これで完了です。それ以外の場合、$ T + e $にはサイクルが含まれます。そのサイクルには、必ず少なくとも1つのエッジ$ e “\ neq e $が含まれます（実際には、少なくとも2つ含まれます）。$ T + ee” $は、 $を含むスパニングツリーです。 e $。
$ T + ee “$が実際にはスパニングツリーであることを証明する必要があります。
回答
ツリーにエッジを追加すると、一意のサイクルが発生します。このサイクルから任意のエッジ（追加したものとは異なる）を削除して、ツリーを元に戻すことができます。この新しいツリーには、追加されたエッジが含まれています。
コメント
- その'はまさに私が言ったことです！
- はい、でも少ない単語で言いました。：）
- 7つの文を本当に 3つにまとめる必要があるためです。 5つあります。サイト上の数千の未回答の質問-'必要のない質問に重複した回答を投稿するよりも、それらのいくつかに回答する方がはるかに優れています。
- 次に、既存の回答をお読みくださいs自分のものを投稿する前に。
- 本当に必要なものはありません-とにかく、どうすればそれを強制できますか？しかし、一般的に、答えは何か新しいことに貢献するはずであり、'わからない場合は、'それを行っていることをどのように知ることができますか'はすでに何と言っていますか？ 'は、2つだけでは大したことではありませんが、すべて同じことを言っている複数の回答があると、ページが乱雑になります。短い要約スタイルの回答を投稿することは、既存の回答が長い場合に間違いなく価値があります。 'この特定のケースでは何も追加されないと思います。