# Thread: Graph theory - Euler or not

1. ## Graph theory - Euler or not

I've stumbled upon this question in Discrete math:
G is a simple graph with Vertices labeled {1,2,3,4,5,6,7}. It is given that G is Euler (that is, G has a Euler circuit) It is also given that there is no edge between vertices 1 and 2, 2 and 3, and 1 and 3. If we add G those edges, the graph we get is:

1. Euler (that is, still contains a euler circuit)
2. Not Euler, but contains a Eulerian trail.
3. Not Euler, no Eulerian trail.
4. Might be Euler, might not be. It depends on the original graph G
5. It is not possible that G is Euler, because according to the data given, it is not a connected graph.

I think it's number 4, because I could draw the graph G in multiple ways according to the given Data, sometimes Getting a Euler circuit and sometimes not. However, I'm not sure about it. Mainly because I don't know whether it is Critical that a graph be connected for it to be Euler (they usually refer to connected graphs, but it's unclear whether it's critical for the definition of Euler).
Help would be much appreciated

2. ## Re: Graph theory - Euler or not

The problem statement says that the the degree of every vertex is even in the original graph. Added edges preserve this property. If Eulerian means the existence of a Eulerian cycle, then the original graph is connected; therefore, the resulting graph is also connected and since all degrees are even, a Eulerian cycle exists there as well. If Eulerian means that all degrees are even, then this is also true in the resulting graph.

3. ## Re: Graph theory - Euler or not

Though, can't there be a Eulerian Cycle without the original graph being connected? Say if vertex 1-3 is disconnected from the rest, and vertex 4-7 is an Eulerian Cycle?

4. ## Re: Graph theory - Euler or not

I addressed this: If Eulerian graph means that all degrees are even (but the graph is not necessarily connected), then this is also true in the resulting graph. That is, whether the original graph is Eulerian in the strong or the weak sense, the resulting graph is Eulerian in the same sense.

5. ## Re: Graph theory - Euler or not

Yes you're right, I'm sorry I've been over this for some time now, so It got a little bit mixed up in my head.

Thank you!

6. ## Re: Graph theory - Euler or not

Originally Posted by coacherez
Though, can't there be a Eulerian Cycle without the original graph being connected? Say if vertex 1-3 is disconnected from the rest, and vertex 4-7 is an Eulerian Cycle?
All depends upon definitions. Have a look at this , in particular points one & two under properties.

Now look at these two graphs:
Attachment 37751 Attachment 37752

The first graph meets all requirements given in the problem. It contains an Eulerian Cycle any trace includes every edge exactly once and begins and ends at the same vertex. However, it is not connected. It contains vertices of degree zero.

The second graph does not meets all requirements given in the problem. It does not contains an Eulerian Cycle. However, it is not connected. It does not contains vertices of degree zero.

7. ## Re: Graph theory - Euler or not

Precisely, It depends upon definitions. I'm pretty sure it's answer number 1, however I might just have to make sure with my instructors. Thank you!