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?

I'm having difficulty with this issue that I saw on an internet site, please help me.

  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. We're not particularly looking for questions that are just the statement of an exercise-style task and a request for us to show you the solution. Also, we are a question-and-answer site, so we require you to formulate a specific question about your situation. "Please help me" is too open-ended to be a good fit here. $\endgroup$
    – D.W.
    Nov 3 '20 at 20:54
  • 2
    $\begingroup$ 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. $\endgroup$
    – plop
    Nov 3 '20 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.