Loading AI tools
Bipartite graph where each node of 1st set is linked to all nodes of 2nd set From Wikipedia, the free encyclopedia
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.[1][2]
Complete bipartite graph | |
---|---|
![]() A complete bipartite graph with m = 5 and n = 3 | |
Vertices | n + m |
Edges | mn |
Radius | |
Diameter | |
Girth | |
Automorphisms | |
Chromatic number | 2 |
Chromatic index | max{m, n} |
Spectrum | |
Notation | K{m,n} |
Table of graphs and parameters |
Graph theory itself is typically dated as beginning with Leonhard Euler's 1736 work on the Seven Bridges of Königsberg. However, drawings of complete bipartite graphs were already printed as early as 1669, in connection with an edition of the works of Ramon Llull edited by Athanasius Kircher.[3][4] Llull himself had made similar drawings of complete graphs three centuries earlier.[3]
A complete bipartite graph is a graph whose vertices can be partitioned into two subsets V1 and V2 such that no edge has both endpoints in the same subset, and every possible edge that could connect vertices in different subsets is part of the graph. That is, it is a bipartite graph (V1, V2, E) such that for every two vertices v1 ∈ V1 and v2 ∈ V2, v1v2 is an edge in E. A complete bipartite graph with partitions of size |V1| = m and |V2| = n, is denoted Km,n;[1][2] every two graphs with the same notation are isomorphic.
K3,3 | K4,4 | K5,5 |
---|---|---|
![]() |
![]() |
![]() |
![]() 3 edge-colorings |
![]() 4 edge-colorings |
![]() 5 edge-colorings |
Regular complex polygons of the form 2{4}p have complete bipartite graphs with 2p vertices (red and blue) and p2 2-edges. They also can also be drawn as p edge-colorings. |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.