Are there at least $|V|$ Eulerian tours in $G$ if $G$ is even degree and connected? (My proof)

39 Views Asked by At

I believe there to be at least $|V|$ Eulerian tours in $G$ if $G$ is even degree and connected, and want to confirm that my reasoning of this is sound. (I am using the definition of Eulerian tour to be a sequence of edges such that each edge is used once, every edge in $G$ is used, and the last edge directs to the starting vertex of this tour). If this is the case of $G$, then there is an Eulerian tour in $G$, and we can enumerate the vertices thereof as $v_1, v_2 \cdots, v_1$, as every vertex lies on the Eulerian tour. We could start an Eulerian tour from any vertex in this enumeration- the vertices describing the Eulerian tour starting from an arbitrary vertex in this enumeration would just continue in the way they are enumerated, but then when the end of this enumeration is reached, we continue this tour from $v_1$, and end where we started from. Therefore there are at least $|V|$ Eulerian tours in $G$, as we can start one from any vertex.

I am wondering if this is correct, as I haven't seen a mention of this fact before, but this might be because it is obvious and not worthy of explicitly mentioning.