1
$\begingroup$

I already have the solved the following questions. Just need to confirm my answers.

Question 1: Prove that a connected graph G with at least two vertices is connected has an Euler circuit if and only every vertex of G has even degree.

My Solution: Let G have vertices of all even degree. (Degree $ = 2x$). Now we can travel multiple times to and away from any vertex. And as the number is even we can always use the last edge to travel to a new edge hence getting to every vertex.

Let G contain a Euler Circuit. For G to contain a Euler Circuit one needs to travel on every edge ending back at the first vertex. Let G contain a vertex with an odd degree. (Degree $= 2x + 1$). Now one can travel to and fro from that vertex but ultimately one would be trapped on that vertex / or if one starts at that vertex one won't be able to reach that vertex hence a vertex can't have a odd degree. (Contradiction). Hence all the vertices have an even degree.

Question 2: Prove that a connected graph has an Euler path if and only if it has exactly two vertices of odd degree.

My Solution: Using the first question if a Graph has vertices with even degree the Graph contains a Euler Circuit. Let G contain a Euler path. Now a graph contains a Euler path if it can travel each vertex but does not end up on the same vertex. Hence there is an additional edge (That makes two vertices have an odd degree).

Let G have two vertices that have odd degree and the rest have even degree. Case I: If we start from an even degree vertex we will be trapped on a vertex on the odd degree vertex as ultimately we will have an edge to travel to the vertex but no edge to travel away from it.

Case II: If we start from the odd degree vertex we can travel on every edge and use the last edge of the first vertex to travel away from that vertex to the other vertex with the odd degree hence completing the Euler path.

$\endgroup$
  • $\begingroup$ Your reasoning is correct, but is not rigorous enough to constitute a proof. For example proposition from the first question does not work for disconnected graphs, but you don't use the assumption that the graph is connected. I know where you would like to use it, but it's not there and that's my point. $\endgroup$ – dtldarek Dec 6 '14 at 9:39
  • $\begingroup$ But the question already states that the graph is connected. So should we use that assumption. $\endgroup$ – George J. Adams Dec 6 '14 at 9:40
  • $\begingroup$ You ought to give a reason why you will be able to visit every vertex of the graph. Indeed you should use the fact that the graph is connected, but that's not all. For example, let's assume that we could split $V$ into three disjoint parts $V=A\uplus B\uplus C$, so that any path between $A$ and $C$ goes through $B$. How do you know that you won't finish $B$ before $A$ and $C$, and then you won't be able to reach $C$ from $A$? It won't happen - the theorem is true - but you have to argue it can't happen (i.e. that all the vertices will be reached). $\endgroup$ – dtldarek Dec 6 '14 at 18:24
  • $\begingroup$ Can you actually help me with the solutions then. :) $\endgroup$ – George J. Adams Dec 6 '14 at 18:26
  • $\begingroup$ I can, but not today. Perhaps tomorrow, certainly on Monday. $\endgroup$ – dtldarek Dec 6 '14 at 18:32
1
$\begingroup$

Hint for question 1:

  • $(\text{circuit} \Rightarrow \text{degrees})$ Direct the circuit, prove that for any vertex we have the in-degree equal to the out-degree, hence their sum must be even.
  • $(\text{circuit} \Leftarrow \text{degrees})$ One of many possible ways is to use induction on the number of edges.
    1. Find any cycle $C$.
    2. If it is an Euler circuit, you are done.
    3. If it is not, remove it from the graph (the remaining part has fever edges and still even degrees).
    4. Process each connected component separately to obtain an Euler circuit for it (we can because of inductive hypothesis).
    5. Merge the circuits using cycle $C$.

Hint for question 2:

  • If you have two vertices of odd degrees, you can add a new vertex which is adjacent to both of them.
  • If you have an Euler path, you can add a new vertex and make it an Euler cycle.

I hope this helps $\ddot\smile$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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