Take the 2-minute tour ×
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.

Graph theory question one of those obvious math proofs so its going to be a pain to prove.

Show that G=(V,E) has an Euler trail between (different) vertices u and v if and only if G is connect and all vertices except u and v are of even degree.

By obviousness if there all other vertices are of even degree then you can make a circuit from v to a1 to a2 to an eventually you will come back to u or v if you continue doing this you eventually will arrive at u or v with no way to leave thus Euler trail.

But how would you actually prove this?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Method 1:

Hint: Use the extremal principle. Consider the longest path.

Method 2:

Hint: Induct on the number of paths.

Method 3:

Hint: Connect $u$ with $v$, and apply the proof of Euler circuit.

share|improve this answer
    
im going to need to look up an example of a proof =\ alright at least i know what to look up ty. –  Faust7 May 15 '13 at 3:16
    
@Faust7 You should be able to use methods 1 or 2, which are independent of each other. Those are direct / immediate, esp the induction proof. –  Calvin Lin May 15 '13 at 3:17

The way to proof goes is as follows. The book I am using gives a max-length contradiction argument to prove that if all vertices of a graph are even then Graph must have Eulerian Circuit.

Claim: The graph with all even vertices has a circuit.

By contradiction, you start by assuming that $T$ a trail of maximum length such that $T = (u=u_1,u_2....,u_k=v)$. Since whenever the vertex $v$ is encoutered on $T$ it has both an incoming and outgoing edge the last time it is encountered will lead it to have an odd degree. Thus either you have another vertex after $v$ in which case the trail you started with is not a maximum length trail or $u=v$ in which case you have a circuit $C$.

For sake of contradiction pick the largest circuit in the graph. Assuming that $C$ is not a Eulerian circuit consider the graph $G-C$. Since the circuit reduces the degree of every vertex by exactly two what $G-C$ gives you is a possibly disconnected graph with all vertices of degrees smaller by 2. Thus each component of $G-C$ has all even vertices and is connected to original circuit $C$ on a vertex say $x$ for component $G_x$. Using the same procedure as above you can construct an new Circuit $C'$ at $x$ inside the component $G_x$. By concatenating this new circuit at $x$ to the older circuit $C$ you get a larger circuit than before which is a contradiction with the fact that $C$ was supposed to be the largest circuit in the graph.Thus the graph with all even vertices will have an Eulerian circuit.

If you are not very fond of proof by contradiction you can think of this as recursively appending circuits of various components till all edges are part of the circuit.

More detailed by someone at university of texas

share|improve this answer
    
im fairly comfortable enough with proofs that i will probably go over all of them n just use the quickest =) tyvm for your help. when i get them figured out i will edit n post them =) –  Faust7 May 15 '13 at 3:24

Your Answer

 
discard

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.