0
$\begingroup$

Can an Euler circuit with ten edges, two vertices of degree 2 and the rest of vertices with the same degree exist?

My approach is that it can't exist since for any Euler circuit you need that every vertex has a pair degree, since one edge will leave the vertex and at the end the other one will enter the vertex. So if you have 2 vertices of degree 2, you have used 4 of the ten edges possible. You need to arrange 6 edges taking into consideration their degree must be pair, so you have 3 vertices with degree 2 but if you connect them to the other 2 vertices, you end up with vertices with different degrees.

$\endgroup$
3
$\begingroup$

enter image description here

The two green vertices have degree $2$, whilst the rest has $4$, and there are $10$ edges in total.

Note that for an Euler path to exist, you only need the vertices to have even degree. They don't have to be of degree exactly $2$.

$\endgroup$
4
  • $\begingroup$ Thanks. Is there a way to calculate the total number of graphs with these restrictions? $\endgroup$ – Rolando González Jun 6 '20 at 23:25
  • $\begingroup$ The sum of the degrees of all vertices is equal to twice the number of edges. So if we have two vertices of degree $2$, and $k$ vertices of degree $n$, we would need $4 + kn = 20$, i.e. $kn = 16$. Thus, $n$ can only be $2,4,8,16$ with $k=16/n$. $\endgroup$ – glowstonetrees Jun 12 '20 at 11:22
  • $\begingroup$ $n=16$, $k=1$ is clearly not possible. $n=2$ corresponds to just having $10$ vertices joined together in a circle. It should also be obvious that the only configuration for $n=8$, $k=2$ is \begin{align} & \equiv \\ 0 = 0 & \equiv 0 = 0 \end{align} where the $0$ represent vertices. $\endgroup$ – glowstonetrees Jun 12 '20 at 11:27
  • $\begingroup$ Finally, we have the $n=k=4$ case as shown above, hence there are $3$ such graphs in total. $\endgroup$ – glowstonetrees Jun 12 '20 at 11:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.