Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I must find out for what values of n and m the complete bipartite graph K(n,m) is eulerian.Can you give me some sugestions or hints to where to start ?I know the definitions but I don't know where to begin to solve this problem.

share|cite|improve this question
up vote 1 down vote accepted

Hint: A connected graph is Eulerian if and only if every vertex has what property?

share|cite|improve this answer
every vertex has even degree – user910 Feb 1 '13 at 13:21
@EmilGrigore Not the same degree--rather, if and only if every vertex has even degree. – Andrew Uzzell Feb 1 '13 at 13:24
so the number of edges must be even – user910 Feb 1 '13 at 13:27
@EmilGrigore Yes, that's true--but is that enough? – Andrew Uzzell Feb 1 '13 at 13:37
well every vertex from K has the same number of edges as the number of vertexes in the opposed set of vertexes.So for example:if one set contains 1,2 and another set contains 3,4,5,6,the vertexes 1,2 will have each 4 edges and the vertexes 3,4,5,6 will each have 2 vertexes.For it to be an eulerian graph,also the sets of vertexes needs to contain an even number of vertexes. – user910 Feb 1 '13 at 13:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.