- Thread starter
- #1

**[SOLVED]Graph theory proof**

**The graph G has precisely two vertices x and y of odd degree. A new graph of multigraph H is formed from G by adding an edge xy. If H is connected, prove that G is connected.**

Please check my following proof for this problem.

Since G has exactly two odd vertices, there is an Euler walk between x and y.

Denote this walk by xEy, where E is a string of vertices.

A walk between two vertices in H either (1)contains edge xy or (2)does not contain edge xy.

(1)Let a, b be two vertices connected via edge xy, so aAxyBb, A and B being strings of vertices.

But then there is a walk from a to b in G, by way of aAxEyBb.

(2)If a walk between two vertices that does not contain edge xy exists in H, it also exists in G.

Hence, any two vertices connected in H are connected in G. Therefore, if H is connected, G is connected.

Last edited: