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.

  • $\begingroup$ 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. $\endgroup$ – Theo Bendit Nov 27 '17 at 0:56
  • $\begingroup$ @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. $\endgroup$ – Morteza Soltani Nov 27 '17 at 1:00
  • $\begingroup$ What do you mean by Eulerian Graph? $\endgroup$ – GhD Nov 27 '17 at 1:09
  • $\begingroup$ @GhD A connected graph $G$ is Eulerian if all the vertices of $G$ have even degree. $\endgroup$ – Morteza Soltani Nov 27 '17 at 1:16
  • 1
    $\begingroup$ @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. $\endgroup$ – Morteza Soltani Nov 27 '17 at 7:53

Your Answer

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

Browse other questions tagged or ask your own question.