Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Consider a complete tripartite graph $K_{\ell,m,n}$

a. Please draw $K_{2,2,3}$.
b. For general values of $\ell,m$, and $n$, how many vertices are in $K_{\ell,m,n}$?
c. How many edges are in $K_{\ell,m,n}$?
d. For what values of $\ell,m$ and $n$ does $K_{\ell,m,n}$ have an Euler circuit?
e. For what values of $\ell,m$ and $n$ does $K_{\ell,m,n}$ have an Euler trail?

I just know the answer for a , am I correct ? Any ideas for other parts ?

enter image description here

share|cite|improve this question
At this link you can start learning how to use $\LaTeX$ to write the mathematics more readably. – Brian M. Scott Dec 13 '12 at 5:29
up vote 3 down vote accepted

(a) Your graph is correct, but it would help if you identified the three sets of vertices. They should be grouped as in the diagram below:

                    1             1  

                  2                 3  

                       3        2

(b) Trivial.

(c) Let the vertex classes of $K_{\ell,m,n}$ be $V_\ell,V_m$, and $V_n$, containing $\ell,m$, and $n$ vertices, respectively. Each vertex in $V_\ell$ is joined by an edge to each vertex in $V_m\cup V_n$, so each vertex in $V_\ell$ has degree $m+n$, and the sum of the degrees of the vertices in $V_\ell$ is $\ell(m+n)$. In similar fashion you can calculate the sums of the degrees of the vertices in $V_m$ and $V_n$ and add them to get the sum of the degrees of all of the vertices in $K_{\ell,m,n}$; then use the handshaking lemma to find the number of edges.

(d, e) A graph has an Euler circuit (or trail) if and only if the degrees of its vertices satisfy a certain condition, and in (c) we saw how to calculate the degrees of the vertices; just combine this information properly.

share|cite|improve this answer
Thanks,man, really helpful – Node.JS Dec 13 '12 at 7:22
@Hooman: Glad to help. – Brian M. Scott Dec 13 '12 at 7:25

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.