グラフの証明を教えてください

質問

背理法の証明で
連結で、全ての頂点次数が偶数であり、オイラーツアーを持たないグラフがあるとするときの
そのうち最も辺の少ないグラフをＧとします
Ｇの中のツアーで中で、最も辺の数が多いものをＣとします。

そのときＧからＣの辺をすべて取り除いたグラフの連結成分Ｈがあるとしたとき
Ｈの各頂点の次数は偶数である。

この証明を教えてください。

回答No.5

Tacosan

そ～なんですよ～, 「ツアー」とか「トレイル」ってあんまり使わない表現なので意味を確認しないとダメなんですよね～＞#4.

ということで, 最低限「ツアー」と「トレイル」の定義は書いてください.

回答No.4

B-juggler

ゴメン、Ｎｏ．１，２です。

頓珍漢なこと書いてる。

Ｃ　は　Ｇの一部と考えればいいのか。

すいません、訂正してお詫びいたします。

ツアー　とか　トレイル　って　グラフや生成木、枝　なんていう日本語と

どう対応しているんだろうか？

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

回答No.3

graphaffine

当たり前だと思うのだが。
Gの点は全て偶点、そして、Cが通る点をxとすればxに接続するCの辺は偶数本、従って、Cの辺を取り除いたときxには偶数本の接続辺が残る。

回答No.2

B-juggler

Ｎｏ．１です。

う～ん、「分かるところまで書いてください」と、書いて

説明されてもなぁ？

どこがどういう風に分からないか？

これになっていない気がするんだけど。

まぁいいや、問題文はこれであっている？

ＧとＣ　が　逆になっていないか？

まぁ意味が分かればどうとでもなるのだが・・・。

基本線、一筆書きができる状況なんだから

（オイラーツアーを持たないって単純にはこういうこと）、

ＧもＣ　も　一筆書き出来ているはず。

まずそこさえ分かっていれば、えっとＣ　か　ここでは？

Ｃ　は　重複線がある状態だね。

　＃Ｇは重複線がない状態だと考えてよさそうだ。

　＃だから逆じゃないかと思ってみているんだけど。

問題の最初に、背理法を使うと書いてあるんだから、

背理法を使ったら？

Ｈの各頂点次数を、偶数ではない（つまり奇数）としておいて、

それが、成立しないことを示せばいい。

次数全て奇数の点におけるグラフは、一筆書きできる？

これで済ませてもいいと思うよ。

何か重大なところで落としているから、しっかり拾ってこようか。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

σ(・・*)は専門ではないから、講師先生に聞いて確認ね。

回答No.1

B-juggler

代数学の元非常勤です。

えっと、明らかに大学のグラフ理論だけど

「どこまで分かるか」を書いてください。

ここで講義するわけにも行かないのでね。

オイラーツアー　って、なんだろう？

頂点次数　ってなんだろう？

これだけの問題を、簡単に丸投げされると、

答えようがないよ。

この講義をやっている先生はきっと悲しいだろうね・・・。

(=^. .^=)　ｍ（＿　＿）ｍ　(=^. .^=)

補足

オイラーツアーは連結グラフGのトレイルで、Gの辺を総て含むもの
頂点次数は各頂点に対応する辺の数です
簡単な図にしたら偶数しかないことはわかるのですが
どうやって証明にしたらいいかがわかりません