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.
Best Answer
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.