I have been tasked with coming up for algorithms for the following graphs if they are Eulerian:
- Cyclic - this is easy - All cyclic graphs are Eulerian and can be traversed in order from 1 to $n$.
- Complete - I am stuck - I know that all cyclic graphs with an odd number of vertices are Eulerian, but I cannot come up with an algorithm that works for any $n$ odd vertices.
- Bipartite - I am stuck - I know that all bipartite graphs where both $m$ and $n$ are even are Eulerian, but again I cannot come up with an algorithm.
Please help lead me on to a path for finding algorithms for complete and bipartite Eulerian graphs.
Hint: For complete graphs, consider a proof by induction. In the inductive step, consider $K_{2k + 1}$. Name its vertices to be $a, b, v_1, v_2, \ldots, v_{2k - 1}$. Now by the inductive hypothesis, we know that the subgraph $K_{2k - 1}$ induced by the vertices $v_1, \ldots, v_{2k - 1}$ contains an Eulerian circuit, say $C$. So to construct an Eulerian circuit for $K_{2k + 1}$, start at $v_1$ and follow the Eulerian circuit $C$ so that you end up back at $v_1$. After doing this, traverse the remaining edges by visiting the vertices in the following order: $$ v_1 \to a \to v_2 \to b \to v_3 \to a \to v_4 \to b \to \cdots \to v_{2k - 1} \to a \to b \to v_1 $$
Try something similar for your last question.