Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

New to graph theory proofs would like some help.

Let $G_{1}$ and $G_{2}$ be Eulerian graphs . let $v_{1}$ be a vertex in $G_{1}$ and $v_{2}$ be a vertex in $G_{2}$ jion $v_{1}$ and $v_{2}$ by a single edge.

1)Does the graph have a Euler trail? EDIT:

I think i finally get this part start at $v_{1}$ make a Euler circiut back to $v_{1}$ ignoring the new path to $v_{2}$ now delete these edges and cross form $v_{1}$ to $v_{2}$ now complete that euler circiut jion the ends together of these 2. Now as shown this is actually a Eulerian Trail. Which is where my confusion arose form.

2) is the resulting graph eulerian? why or why not?

The requirements for a graph to be Eulerian is that every vertex is of even degree, and clearly this was true in $G_{1}$ and $G_{2}$ as they where Eulerian thus all vertex of $G_{1}$ and $G_{2}$ where even. even +1 is not even hence there The new Graph is not Eulerian. ($ v_{1}$ and $v_{2}$ must both be of odd degree)

share|cite|improve this question
In 1), you seem to be using a definition where a trail must end where it begins, but I don't think that's the usual definition. – Gerry Myerson May 15 '13 at 13:45
can i still use it? theres no way we can start and end at the smae point because only 1 link between G1 and G2 i didnt know how to prove it so i just wrote that down? – Faust7 May 15 '13 at 13:53
The question asked whether the graph has an Euler trail. If the person asking the question doesn't mean the same thing as you mean by the phrase, "Euler trail," your answer will not be an answer to her question. Right? – Gerry Myerson May 15 '13 at 14:03
no but i thought a euler trail had to begin and end at the same place or it wasn't a euler trail. sorry i misinterpreted what do they want me to show? – Faust7 May 15 '13 at 14:17
An Euler circuit begins and ends at the same vertex. (An Euler trail may or may not.) – Douglas S. Stones May 15 '13 at 14:56
up vote 4 down vote accepted

It is important that the definition of an Eulerian graph here includes the property "is connected". Without this property, we can have the following situation where $G_1$ is the blue graph and $G_2$ is the red graph, and we add in the orange edge:

A possible non-Eulerian resultant graph

Both $G_1$ and $G_2$ contain an Eulerian cycle, but the resultant graph does not contain an Eulerian trail.

We conclude that we must use the assumption that $G_1$ and $G_2$ are connected, otherwise the claim is not true due to the above counterexample.

For 1., you seem to be confusing Eulerian trail with Eulerian circuit. Assuming $G_1$ and $G_2$ are connected, there is an Eulerian trail (and even an Eulerian circuit) starting at any vertex, and we can join them together as described.

You can also approach 1. theoretically by using the following result:

An undirected graph has an Eulerian trail if and only if at most two vertices have odd degree, and if all of its vertices with nonzero degree belong to a single connected component. (Source: Wikipedia)

Since the vertices of $G_1$ and $G_2$ have even degrees, the resultant graph has two odd degree vertices. It is also connected since $G_1$ and $G_2$ are connected. So the resultant graph satisfies the above condition, and thus contains an Eulerian trial.

Your approach to 2. seems natural, but I don't think the conditions are right, e.g. this non-Eulerian graph has every vertex of even degree:

non-Eulerian graph with every vertex of even degree

This is what it should be:

An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component. (Source Wikipedia, op. cit.)

share|cite|improve this answer
Thank you that is a very good explanation! – Faust7 May 15 '13 at 16:14

1) Yes. Take the Eulerian circuit, and delete that edge. You get a eulerian path.

2) No. Use the classification that a graph is Eulerian if and only if every vertex has even degree.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.