Math 2.0

Combinatorics Graph theory: basic notions Example

Complete bipartite graph

Example

Let mm and nn be natural numbers. The complete bipartite graph Km,nK_{m,n} is the graph whose vertex set is a disjoint union A⊔BA \sqcup B with ∣A∣=m|A| = m and ∣B∣=n|B| = n. Two vertices are adjacent if and only if one is in AA and the other is in BB.

Remarks

Km,nK_{m,n} has m+nm + n vertices and mnmn edges. It is bipartite with parts AA and BB. For m,n≥1m, n \ge 1 its chromatic number is 22. K1,nK_{1,n} is a star. K3,3K_{3,3} is not planar.

Where this leads

5 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Complete_bipartite_graph, Definition
About this page
Tag0V0GC7BQAN
URIm2://0V0GC7BQAN
Kindexample
WritingW2 usable
MSC05C99
Instance ofGraph
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W3

  • a person confirmed each agent-written section: rule P04 (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by