Bipartite graph. average degree. Euler circuit.

Question

This is such a hard question to get my head around. Can anyone help solve this?

Answer 1

Consider the following: If you have $m+n$ vertices and the bipartite graph is complete, then you can send an edge from each of the $m$ vertices on one side to each of the $n$ vertices on the other side. Since for each $m$ you have $n$ possibilities, then $e(K_{m,n})=mn$.

Now the degree of each vertex on the $V_0$ side is $n$ since the graph is complete bipartite. Then a vertex on $V_0$ is connected to each of the $m$ on $V_1$. The same reasoning applies to the vertices on $V_1$, the degree for each vertex on $V_1$ is $m$. It follows that the average degree is $\dfrac{m+n}{2}$.

EDIT: I got the numbers messed around. Thanks @bof for the comment.

The average degree is NOT $\dfrac{m+n}{2}$. The average degree is $\dfrac{2mn}{m+n}$. This is because the sum of the degrees of $V_0$ is $\displaystyle\sum_{i=1}^mn=mn$ and the sum of the degrees on $V_1$ is $\displaystyle\sum_{i=1}^nm=nm$. Then, we add these quantities and divide by the total number of vertices to obtain $\dfrac{mn+nm}{m+n}=\dfrac{2mn}{m+n}$.

Now, a graph has an Eulerian circuit if each vertex has even degree. Then for even values of $m$ and $n$, $K_{m,n}$ will have an Eulerian circuit.

EDIT: Thanks again for the correction @bof. Indeed, we requiere the graph to be connected for the condition to hold.

I think that this other links can help you as well:
Hamilton,Euler circuit,path
eulerian bipartite complete graph
http://www.maths.lse.ac.uk/Personal/jozef/MA210/07sol.pdf