# Graph Theory - Euler circuit , trail

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 ?

-
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

(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             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.

-
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