Turán graph
Turán graph is a complete multipartite graph for partitions whose sizes are as equal as possible.
All 1 facts, and where they come from
Facts
1 facts · 0 confirmed by two sources · 0 cited · 1 from one source
Where this comes from
Papalocal keeps its own record. It started from these sources; what each one said is kept here as it was copied, so a change on their side never changes this page by itself. Tap one to read its version.
What Wikidata says · copied November 17, 2026 · revision 2506236616
- Described as
- complete multipartite graph for partitions whose sizes are as equal as possible
- Other names
- Turan graph
- Named after
- Pál Turán
- Wikipedias with a page
- 13
Wikidata item Q720459 (wikidata.org/wiki/Q720459), public domain (CC0). Copied 2026-11-17.
What Wikipedia says · copied November 17, 2026 · revision 1370118236
The Turán graph, denoted by T(n,r), is a complete multipartite graph; it is formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to different subsets. Where q and s are the quotient and remainder of dividing n by r (so n=qr+s), the graph is of the form Kq+1,q+1,…,q,q, and the number of edges is
(1−1r)n2−s22+(s2).
The edge count can be more succinctly stated as ⌊(1−1r)n22⌋. The graph has s subsets of size q+1, and r−s subsets of size q; each vertex has degree n−q−1 or n−q. It is a regular graph if n is divisible by r (i.e. when s=0).
From the Wikipedia article “Turán graph” (en.wikipedia.org/wiki/Turán_graph), by its contributors, under CC BY-SA 4.0 (creativecommons.org/licenses/by-sa/4.0/). Copied 2026-11-17; not changed.
Confirmed Two sources agree. Cited One source, and it names where it got it. One source One source, without a reference of its own. Sources disagree The sources disagree. We show the best-supported value and keep theirs below.
Picture: Wikimedia Commons: Turan 13-4.svg · See Commons file page
