A complete bipartite graph is a type of graph in which the vertices can be divided into two sets, such that every vertex in one set is connected to every vertex in the other set. In other words, there are no edges within each set, only between the two sets. This type of graph is denoted as Kn,m, where n and m represent the number of vertices in each set.
A complete bipartite graph with n vertices in one set and m vertices in the other set has n x m edges. This is because each vertex in one set is connected to all vertices in the other set, resulting in n x m total connections.
The degree sequence of a complete bipartite graph is (m, m, ..., m, n, n, ..., n), where there are m vertices with degree n and n vertices with degree m. In other words, the degree sequence alternates between the two sets of vertices.
Complete bipartite graphs can be used to model relationships between two distinct groups, such as male and female students in a school or buyers and sellers in a market. They can also be used in scheduling problems, as each set of vertices can represent a different group of tasks or resources.
No, complete bipartite graphs are not planar. This is because they contain a subgraph that is isomorphic to K3,3, which is known to be non-planar. In other words, it is impossible to draw a complete bipartite graph on a plane without any edges crossing.