Circle within sub-graph of $K_n$

Question

Let a complete graph, $K_n$ and a sub-graph, $G$. It's given that $G$ doesn't contain an Eulerian cycle. Why is it implying the number of edges is at most $n-1$?

Answer 1

Prove by induction on $n$. Suppose every subgraph of $K_n$ which does not contain an Eulerian cycle has at most $n-1$ edges.

Suppose for contradiction that $K_{n+1}$ has a subgraph $G$ with $n+1$ edges that does not contain an Eulerian cycle. Note that if every vertex in $G$ has valence greater than $1$, then there must exist an Eulerian cycle contained in $G$, and so there must exist a vertex $v\in V(G)$ such that the valence of $v$ is at most $1$. Can you complete this inductive argument?

The base can can be done for $n=2$ easily enough.