0
$\begingroup$

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.

$\endgroup$
8
  • $\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$ Nov 27, 2017 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$ Nov 27, 2017 at 1:00
  • $\begingroup$ What do you mean by Eulerian Graph? $\endgroup$
    – GhD
    Nov 27, 2017 at 1:09
  • $\begingroup$ @GhD A connected graph $G$ is Eulerian if all the vertices of $G$ have even degree. $\endgroup$ Nov 27, 2017 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$ Nov 27, 2017 at 7:53

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .