0
$\begingroup$

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

  • 1
    At [this link](http://meta.math.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference) you can start learning how to use $\LaTeX$ to write the mathematics more readably.2012-12-13

1 Answers 1

3

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

  • 0
    @Hooman: Glad to help.2012-12-13