[Math] Connected graphs, Euler circuits and paths, vertices of odd degree

graph theory

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.

Best Answer

TheHint for question 1:

  • $(\text{Euler circuit} \Rightarrow \text{ even 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{Euler circuit} \Leftarrow \text{even 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$

Related Question