I know that in $K_n$, a complete graph. ALL the vertices must be of even degree for a euler cycle to exist. So n should be odd in this case if we want euler cycles. And if n is even, then $K_n$ has ALL vertices, not just two be of odd degree, so no Euler Trail and Euler Cycle exists. So naturally this causes me to believe that the answer is, no there is no $K_n$ that works here. But what about $K_2$? which is just an edge. Would that work here?
Are there any $K_n$ that have Euler trails but not Euler cycles
eulerian-pathgraph theory
Related Solutions
What you are looking for is a Hamilton cycle decomposition of the complete graph $K_n$, for odd $n$.
An example of how this can be done (among many other results in the area) is given in: D. Bryant, Cycle decompositions of complete graphs, in Surveys in Combinatorics, vol. 346, Cambridge University Press, 2007, pp. 67–97.
For odd $n$, let $n=2r+1$, take $\mathbb{Z}_{2r} \cup \{\infty\}$ as the vertex set of $K_n$ and let $D$ be the orbit of the $n$−cycle
\[(\infty, 0, 1, 2r − 1, 2, 2r − 2, 3, 2r − 3,\ldots , r − 1, r + 1, r)\]
under the permutation $\rho_{2r}$ [Here $\rho_{2r}=(0,1,\ldots,2r-1)$]. Then $D$ is a decomposition of $K_n$ into $n$-cycles.
Here is the starter cycle for a Hamilton cycle decomposition of $K_{13}$, given in the paper:
If you rotate the starter, you obtain the other Hamilton cycles in the decomposition.
The method of using a "starter" cycle under the action of a cyclic automorphism is typical in graph decomposition problems.
Step 1: Start with any vertex $v$ and start moving along unused edges until you return to $v$. Observe that from the condition on the in- and out-degrees, whenever you enter a vertex you are going to be able to go out.
Step 2: Assume you got such a cycle but it didn't use all edges. Let $w$ be a vertex in the cycle used that has an edge that has not been used. Start a cycle from $w$ and using edges that have not been used. Again, this can be done because for every edge not used, incident in a vertex $a$, there is going to be a not used edge coming out of $a$. Insert that new cycle to the old one, in $w$. Repeat this step until all edges are used.
Best Answer
You're correct that a graph has an Eulerian cycle if and only if all its vertices have even degree, and has an Eulerian path if and only if exactly $0$ or exactly $2$ of its vertices have an odd degree. If $n$ is odd, then the first condition is satisfied, and if $n$ is even then all $n$ of the vertices have odd degree. So, this fails both conditions unless $n=2$, so what you've written does not preclude the fact that $K_2$ has an Eulerian path. (In fact, it does, as you can easily see from the definition of Eulerian path.)