1
$\begingroup$

Let m, n be nonzero natural numbers. Define $K_{m,n}$ to be the complete bipartite graph, which has vertex set $V = V_0 ∪ V_1$ such that $|V_0| = m$, $|V_1| = n$, $V_0 ∩ V_1 = ∅$, and edge set consisting of all edges ${a, b}$ with $a ∈ V_0$, $b ∈ V_1$. How many edges does $K_{m,n}$ have? What is the average degree of $K_{m,n}$? For which values of $m$, $n$ does $K_{m,n}$ have an Euler circuit?

Is someone able to help me solve this question thanks in advance.

$\endgroup$
2
  • 2
    $\begingroup$ You might draw the example with $m=2,n=3$ to see what is happening here. Do you understand the terminology in the question? If not, look it up. Where are you stuck? $\endgroup$ May 28, 2017 at 1:41
  • $\begingroup$ I edited the title of your question. Please try to make more descriptive titles in the future. It helps in searching old questions, and it is useful for deciding whether to take a look at a question or not. $\endgroup$ May 28, 2017 at 8:48

1 Answer 1

1
$\begingroup$

The following proofs, while complete, are deliberately kept short and intended as guidelines for you to understand and fill with the left out details.

Claim 1. $K_{m,n}$ has $m \times n$ edges.

Proof (by induction on $m$). For $m=1$ this should be apparent. For $m+1$ note that we can split $K_{m+1,n}$ into disjoint graphs $K_{m,n}$ and $K_{1,b}$ in the obvious way. Hence, by induction hypothesis, $K_{m+1,n}$ has $m \cdot n + m = (m+1) \cdot n$ many edges. Q.E.D.

Claim 2. The average degree of $K_{m,n}$ is $\frac{2mn}{m+n}$.

Proof. There are $m$ vertices with degree $n$ and $n$ vertices with degree $m$. Q.E.D.

Claim 3. $K_{m,n}$ has an Euler circuit iff both $m,n$ are even.

Proof. An connected, undirected graph has an Euler circuit iff the degree of all of its vertices is even. Q.E.D.

$\endgroup$

Your Answer

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

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