# Eulerian Graph with odd number of vertices

I am struggling with the following question:

Prove that for each odd integer $n ≥ 3$, there exists exactly one Eulerian graph of order $n$ containing exactly three vertices of the same degree and at most two vertices of any other degree.

This is how I solved this. Any feedbacks on the answer is highly appreciated:

We prove this by using induction on the graph order $n$. For $n=3$, the graph with degree sequence 2, 2, 2 is the only Eulerian graph. For $n=5$, the graph with degree sequence 4, 4, 2, 2, 2 is the only Eulerian graph. Then for $n$ odd and greater than 5, consider the sequence $n-1,\,n-1,\,d_1+2,\,d_2+2,\,\cdots,\,d_{n-4}+2,\,2,\,2$ is graphical if and only if the sequence $d_1,\,d_2,\,\cdots,\,d_{n-4},\,0,\,0$ is graphical. So, by induction, there is exactly one sequence fitting these criteria which is graphical.

Now, we check that this sequence is Eulerian. Again, by induction, we may assume that the graph $G'$, with degree sequence $d_1,\,d_2,\,\cdots,\,d_{n-4}$ is Eulerian. Let $C'$ be an Eulerian circuit in $G'$. Notice that a graph $G$ with degree sequence $n-1,\,n-1,\,d_1+2,\,d_2+2,\,\cdots,\,d_{n-4}+2,\,2,\,2$ may be constructed from $G'$ by adding four vertices $x_1,\,x_2,\,y_1,\,y_2$ and all of the edges $x_i v$ for $i=1,\,2$, and $v\in V(G')\cup \{y_1,\,y_2\}$, and the edge $x_1 x_2$. Let $v_1 v_2$ be an edge of $C'$ and let $C$ be the circuit given by:

• Follow $v_1 v_2$, then $v_2 x_1$.
• Follow the edges $x_1 v$, then $v x_2$ alternately with $x_2 u$, then $u x_1$ for all vertices $u,\,v\in V(G')\cup \{y_1,\,y_2\}-\{v_2\}$, so that each of these vertices is visited exactly once. Note that since $G$ has odd number of vertices, we visit an even number of vertices in this process, and consequently end at $x_1$.
• Follow $x_1 x_2$, then $x_2 v_2$.
• Follow the rest of $C'$.

Then $C$ is a circuit, which by construction follows every edge in $E(G)-E(G')$, and since $C'$ is an Eulerian circuit, also follows every edge in $E(G')$. Thus $C$ is an Eulerian circuit and $G$ is Eulerian.

• Without thinking too deeply about the problem, my best advice would be to start trying to construct these graphs for small $n$. For instance, for $n = 3$, I can see no other way except a triangle. Nov 27, 2017 at 0:56
• @TheoBendit Thanks for your prompt response. I have tried to construct it for n = 3, 5 and 7 and always there is two vertices of degree 2 in the degree sequence. However, constructing it for any $n$ is my struggle. Nov 27, 2017 at 1:00
• What do you mean by Eulerian Graph?
– GhD
Nov 27, 2017 at 1:09
• @GhD A connected graph $G$ is Eulerian if all the vertices of $G$ have even degree. Nov 27, 2017 at 1:16
• @TheoBendit Thank you anyways for your comment. I work more on it and if I find the right solution, I will share it right here. Nov 27, 2017 at 7:53

Assume the order of the graph is $$2k+1$$, then the possible degree of each vertex is $$2,4,\cdots,2k$$, then by pigeonhole principle we know there are at least 3 vertice have same degree.