# Question about graphs and Eulerian path

An almost complete graph of n vertices is obtained from the removal of two edges of the complete graph of n vertices. For which values of n are there almost complete graphs that admit Eulerian paths?

• Try looking at the parity of the degrees of the vertices. In particular, how many vertices could get odd degree. If there are more than $2$ vertices of odd degree, then there is no Euler path. If there are $2$ or zero there is going to be. There cannot be just $1$ verted of odd degree. by the hand-shaking lemma. If you start if $K_n$ for $n$ even and large ($\geq 8$) too many vertices have odd degree, even when the two edges are deleted. When $n$ is odd, removing the edges produces vertices of odd degree. Choose the edges to remove such that only $2$ vertices of odd degree are produced.