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)?

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

Your Answer

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

Browse other questions tagged or ask your own question.