Papalocal
Loading…
Papalocal · Things
Work

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

Named after
Pál Turán 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

People connected 1

Known for it