A cycle is defined to be a circuit with no repeasted vertex. If a cycle has length k, we talk of a k-cycle. Determine the number of 4-cycles in Km,n where m>2 and n>2.

:(

Printable View

- Dec 8th 2009, 06:55 PMkablamCycles
A cycle is defined to be a circuit with no repeasted vertex. If a cycle has length k, we talk of a k-cycle. Determine the number of 4-cycles in Km,n where m

__>__2 and n__>__2.

:( - Dec 8th 2009, 07:14 PMguildmage
I'm not a graph theorist, but I think since we are considering $\displaystyle K_{m,n}$ for $\displaystyle m,n \geq 2$, then any four distinct vertices -- 2 coming from the set of m vertices and 2 coming from the set of n vertices -- will make a 4-cycle. So that there will be $\displaystyle \left( \begin{array}{l} m \\ 2 \\ \end{array} \right) \left( \begin{array}{l} n \\ 2 \\ \end{array} \right)$ ways of choosing such a collection of 4 vertices.