# complete bipartite graph, circuits

Let $2\leq{m}\leq{n}$ be an integer.

We denote the complete bipartite graph as $K_m,_n$

(a)How many circuits of length 4 contain $K_m,_n$?

(b)How long is the longest circuit in $K_m,_n$?

A bipartite graph, where m is the number of vertices in A and n is the number vertices in B.

A useful characterization of bipartite graphs: A graph G is bipartite if and only if you do not have circuits with an odd number of edges. => If G is bipartite with corners classes A and B, is every other corner in a circuit in A and every other is B. Thus, a circuit having an even number of corners.

in (a) i think for example m=3 and n=5 or m=4 and n=6 (Must be even number of corners). For a circuit of length 4 we will use 2 vertices in A and 2 vertices in B. My best guess, something like: $\binom{m}{2}$*$\binom{n}{2}$

Can someone help me with (a) and (b)?

• $\binom{n}2\cdot\binom{m}{2}$ sounds good. As for the longest cycle, I suppose it's $2m$. – Ivan Neretin Sep 30 '16 at 7:57
• What do you mean by 2m? @IvanNeretin – PerkinsN Oct 2 '16 at 9:00
• I mean just that: two times number $m$. – Ivan Neretin Oct 2 '16 at 9:13