Welcome to our community

Be a part of something great, join today!

Graph theory proof

Yuuki

Member
Jun 7, 2013
43
[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:

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
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.
Frankly I have no idea how that argument works.

Where have you used "G has precisely two vertices x and y of odd degree"?

If \(\displaystyle G\) is not connected then it is the union of at least two components.
Because each component is a sub-graph and any graph has an even number of odd verticies, then \(\displaystyle x\&~y\) belong to the same component.

So how would adding another edge \(\displaystyle xy\) to \(\displaystyle G\) connect it?
 

Yuuki

Member
Jun 7, 2013
43
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.
I used it here.
But I now realize this is a big mistake, because the argument

a graph has two odd vertices [tex]\Rightarrow[/tex] the graph has an Euler walk

is valid only for connected graphs.
I can't use this assumption because that is precisely what I'm trying to prove.

As for the other argument, I tried to separate it into binary cases.
To use the (wrong) Euler circuit argument.


So,

G is not connected.
[tex]\Rightarrow[/tex] There are at least two components.
[tex]\Rightarrow[/tex] Since each component is connected, there must be an even number of odd vertices.
[tex]\Rightarrow[/tex] x and y must belong to the same component because there are only two odd vertices in G.
[tex]\Rightarrow[/tex] Connecting x and y will not connect disjoint components.

Hence, if G is not connected, neither is H, which proves the assumption by contraposition?
 

Plato

Well-known member
MHB Math Helper
Jan 27, 2012
196
G is not connected.
[tex]\Rightarrow[/tex] There are at least two components.
[tex]\Rightarrow[/tex] Since each component is connected, there must be an even number of odd vertices.
[tex]\Rightarrow[/tex] x and y must belong to the same component because there are only two odd vertices in G.
[tex]\Rightarrow[/tex] Connecting x and y will not connect disjoint components.
Hence, if G is not connected, neither is H, which proves the assumption by contraposition?
That is now correct.