241. How many edges do the complete bipartite graph K(m,n) and a k-regular graph on n vertices have?
EasyGraph algorithms
Technical
Show model answer
K(m,n) joins every one of the m left vertices to every one of the n right vertices, so it has m·n edges (and no edges inside either side). For example K(3,3) has 9 edges.
In a k-regular graph every vertex has degree k. By the handshake lemma the degree sum is 2E, so E = n·k/2. Consequently n·k must be even: a 3-regular graph needs an even number of vertices. K_n is (n−1)-regular and K(n,n) is n-regular.