Graph Theory Proof: Connectivity of G Proven

[annie122]

[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.

 

[Plato2]

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 $$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 $$x\&~y$$ belong to the same component.

So how would adding another edge $$xy$$ to $$G$$ connect it?

 

[annie122]

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 $$\Rightarrow$$ 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.
$$\Rightarrow$$ There are at least two components.
$$\Rightarrow$$ Since each component is connected, there must be an even number of odd vertices.
$$\Rightarrow$$ x and y must belong to the same component because there are only two odd vertices in G.
$$\Rightarrow$$ Connecting x and y will not connect disjoint components.

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

 

[Plato2]

G is not connected.
$$\Rightarrow$$ There are at least two components.
$$\Rightarrow$$ Since each component is connected, there must be an even number of odd vertices.
$$\Rightarrow$$ x and y must belong to the same component because there are only two odd vertices in G.
$$\Rightarrow$$ 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.