complete graph bipartite graph A {graph} which has a link between every pair of nodes. A complete {bipartite graph} can be partitioned into two subsets of nodes such that each node is joined to every node in the other subset. (1995-01-24)