Turán's theorem: Difference between revisions

Content deleted Content added

Inline

Revision as of 08:12, 20 November 2020

In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size.

An example of an $n$ -vertex graph that does not contain any $(r+1)$ -vertex clique $K_{r+1}$ may be formed by partitioning the set of $n$ vertices into $r$ parts of equal or nearly equal size, and connecting two vertices by an edge whenever they belong to two different parts. The resulting graph is the Turán graph $T(n,r)$ . Turán's theorem states that the Turán graph has the largest number of edges among all $K r +1$ -free $n$ -vertex graphs.

Turán's theorem, and the Turán graphs giving its extreme case, were first described and studied by Hungarian mathematician Pál Turán in 1941,^[1] although a special case of the theorem was stated earlier by Mantel in 1907.^[2]

Statement

Turán's theorem states that every graph $G$ with $n$ vertices that does not contain $K_{r+1}$ as a subgraph has a number of edges that is at most

{\frac {r-1}{r}}\cdot {\frac {n^{2}}{2}}=\left(1-{\frac {1}{r}}\right)\cdot {\frac {n^{2}}{2}}.

The same formula gives the number of edges in the Turán graph $T(n,r)$ , so it is equivalent to state Turán's theorem in the form that, among the $n$ -vertex simple graphs with no $(r+1)$ -cliques, $T(n,r)$ has the maximum number of edges.^[3]

Proofs

Aigner & Ziegler (2018) list five different proofs of Turán's theorem.^[3]

Turán's original proof uses induction on the number of vertices. Given an $n$ -vertex $K_{r+1}$ -free graph with more than $r$ vertices and a maximal number of edges, the proof finds a clique $K_{r}$ (which must exist by maximality), removes it, and applies the induction to the remaining $(n-r)$ -vertex subgraph. Each vertex of the remaining subgraph can be adjacent to at most $r-1$ clique vertices, and summing the number $(n-r)(r-1)$ of edges obtained in this way with the inductive number of edges in the $(n-r)$ -vertex subgraph gives the result.^[1]^[3]

A different proof by Paul Erdős finds the maximum-degree vertex $v$ from a $K_{r+1}$ -free graph and uses it to to construct a new graph on the same vertex set by removing edges between any pair of non-neighbors of $v$ and adding edges between all pairs of a neighbor and a non-neighbor. The new graph remains $K_{r+1}$ -free and has at least as many edges. Repeating the same construction recursively on the subgraph of neighbors of $v$ eventually produces a graph in the same form as a Turán graph (a collection of $p$ independent sets, with edges between each two vertices from different independent sets) and a simple calculation shows that the number of edges of this graph is maximized when all independent set sizes are as close to equal as possible.^[3]^[4]

Motzkin & Straus (1965) prove Turán's theorem using the probabilistic method, by seeking a discrete probability distribution on the vertices of a given $K_{r+1}$ -free graph that maximizes the expected number of edges in a randomly chosen induced subgraph, with each vertex included in the subgraph independently with the given probability. For a distribution with probability $p_{i}$ for vertex $v_{i}$ , this expected number is $\textstyle \sum _{(v_{i},v_{j})\in E(G)}p_{i}p_{j}$ . Any such distribution can be modified, by repeatedly shifting probability between pairs of non-adjacent vertices, so that the expected value does not decrease and the only vertices with nonzero probability belong to a clique, from which it follows that the maximum expected value is at most $(r-1)/2r$ . Therefore, the expected value for the uniform distribution, which is exactly the number of edges divided by $1/n^{2}$ , is also at most $(r-1)/2r$ , and the number of edges itself is at most $n^{2}(r-1)/2r$ .^[3]^[5]

A proof by Noga Alon and Joel Spencer, from their book The Probabilistic Method, considers a random permutation of the vertices of a $K_{r+1}$ -free graph, and the largest clique formed by a prefix of this permutation. By calculating the probability that any given vertex will be included, as a function of its degree, the expected size of this clique can be shown to be $\textstyle \sum 1/(n-d_{i})$ , where $d_{i}$ is the degree of vertex $v_{i}$ . There must exist a clique of at least this size, so $\textstyle r\geq \sum 1/(n-d_{i})$ . Some algebraic manipulation of this inequality using the Cauchy–Schwarz inequality and the handshaking lemma proves the result.^[3]

Aigner and Ziegler call the final one of their five proofs "the most beautiful of them all"; its origins are unclear. It is based on a lemma that, for a maximal $K_{r+1}$ -free graph, non-adjacency is a transitive relation, for if to the contrary $(u,v)$ and $(v,w)$ were non-adjacent and $(u,w)$ were adjacent one could construct a $K_{r+1}$ -free graph with more edges by deleting one or two of these three vertices and replacing them by copies of one of the remaining vertices. Because non-adjacency is also symmetric and reflexive (no vertex is adjacent to itself), it forms an equivalence relation whose equivalence classes give any maximal graph the same form as a Turán graph. As in the second proof, a simple calculation shows that the number of edges is maximized when all independent set sizes are as close to equal as possible.^[3]

Mantel's theorem

The special case of Turán's theorem for $r=2$ is Mantel's theorem: The maximum number of edges in an $n$ -vertex triangle-free graph is $\lfloor n^{2}/4\rfloor .$ ^[2] In other words, one must delete nearly half of the edges in $K_{n}$ to obtain a triangle-free graph.

A strengthened form of Mantel's theorem states that any Hamiltonian graph with at least $n^{2}/4$ edges must either be the complete bipartite graph $K_{n/2,n/2}$ or it must be pancyclic: not only does it contain a triangle, it must also contain cycles of all other possible lengths up to the number of vertices in the graph.^[6]

Another strengthening of Mantel's theorem states that the edges of every $n$ -vertex graph may be covered by at most $\lfloor n^{2}/4\rfloor$ cliques which are either edges or triangles. As a corollary, the graph's intersection number (the minimum number of cliques needed to cover all its edges) is at most $\lfloor n^{2}/4\rfloor$ .^[7]

References

^ ^a ^b Turán, Paul (1941), "On an extremal problem in graph theory", Matematikai és Fizikai Lapok (in Hungarian), 48: 436–452
^ ^a ^b Mantel, W. (1907), "Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff)", Wiskundige Opgaven, 10: 60–61
^ ^a ^b ^c ^d ^e ^f ^g Aigner, Martin; Ziegler, Günter M. (2018), "Chapter 41: Turán's graph theorem", Proofs from THE BOOK (6th ed.), Springer-Verlag, pp. 285–289, doi:10.1007/978-3-662-57265-8_41, ISBN 978-3-662-57265-8
^ Erdős, Pál (1970), "Turán Pál gráf tételéről" [On the graph theorem of Turán] (PDF), Matematikai Lapok (in Hungarian), 21: 249–251, MR 0307975
^ Motzkin, T. S.; Straus, E. G. (1965), "Maxima for graphs and a new proof of a theorem of Turán", Canadian Journal of Mathematics, 17: 533–540, doi:10.4153/CJM-1965-053-6, MR 0175813
^ Bondy, J. A. (1971), "Pancyclic graphs I", Journal of Combinatorial Theory, Series B, 11 (1): 80–84, doi:10.1016/0095-8956(71)90016-5
^ Erdős, Paul; Goodman, A. W.; Pósa, Louis (1966), "The representation of a graph by set intersections" (PDF), Canadian Journal of Mathematics, 18 (1): 106–112, doi:10.4153/CJM-1966-014-3, MR 0186575

[turan-1] Turán, Paul (1941), "On an extremal problem in graph theory", Matematikai és Fizikai Lapok (in Hungarian), 48: 436–452

[mantel-2] Mantel, W. (1907), "Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff)", Wiskundige Opgaven, 10: 60–61

[az-3] ^ ^a ^b ^c ^d ^e ^f ^g Aigner, Martin; Ziegler, Günter M. (2018), "Chapter 41: Turán's graph theorem", Proofs from THE BOOK (6th ed.), Springer-Verlag, pp. 285–289, doi:10.1007/978-3-662-57265-8_41, ISBN 978-3-662-57265-8

[erdos-4] Erdős, Pál (1970), "Turán Pál gráf tételéről" [On the graph theorem of Turán] (PDF), Matematikai Lapok (in Hungarian), 21: 249–251, MR 0307975

[ms-5] Motzkin, T. S.; Straus, E. G. (1965), "Maxima for graphs and a new proof of a theorem of Turán", Canadian Journal of Mathematics, 17: 533–540, doi:10.4153/CJM-1965-053-6, MR 0175813

[bondy-6] Bondy, J. A. (1971), "Pancyclic graphs I", Journal of Combinatorial Theory, Series B, 11 (1): 80–84, doi:10.1016/0095-8956(71)90016-5

[egp-7] Erdős, Paul; Goodman, A. W.; Pósa, Louis (1966), "The representation of a graph by set intersections" (PDF), Canadian Journal of Mathematics, 18 (1): 106–112, doi:10.4153/CJM-1966-014-3, MR 0186575

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
-In [[graph theory]], '''Turán's theorem''' is a result on the number of edges in a [[complete graph|''K''<sub>''r''+1</sub>]]-[[Glossary_of_graph_theory#Subgraphs|free]] [[Graph (discrete mathematics)|graph]].
+In [[graph theory]], '''Turán's theorem''' bounds the number of edges that can be included in an [[undirected graph]] that does not have a [[clique (graph theory)|complete subgraph]] of a given size.
-An {{mvar|n}}-[[vertex (graph theory)|vertex]] graph that does not contain any {{math|(''r'' + 1)}}-vertex [[clique (graph theory)|clique]] may be formed by partitioning the set of vertices into {{mvar|r}} parts of equal or nearly equal size, and connecting two vertices by an edge whenever they belong to two different parts. The resulting graph is the [[Turán graph]] {{math|''T''(''n'', ''r'')}}. Turán's theorem states that the Turán graph has the largest number of edges among all {{math|''K''<sub>''r''+1</sub>}}-free {{mvar|n}}-vertex graphs.
+An example of an <math>n</math>-[[vertex (graph theory)|vertex]] graph that does not contain any <math>(r+1)</math>-vertex clique <math>K_{r+1}</math> may be formed by partitioning the set of <math>n</math> vertices into <math>r</math> parts of equal or nearly equal size, and connecting two vertices by an edge whenever they belong to two different parts. The resulting graph is the [[Turán graph]] <math>T(n,r)</math>. Turán's theorem states that the Turán graph has the largest number of edges among all {{math|''K''<sub>''r''+1</sub>}}-free {{mvar|n}}-vertex graphs.
-[[Turán graph]]s were first described and studied by [[Hungary|Hungarian]] [[mathematician]] [[Pál Turán]] in 1941, though a [[special case]] of the theorem was stated earlier by Mantel in 1907.
+Turán's theorem, and the [[Turán graph]]s giving its extreme case, were first described and studied by [[Hungary|Hungarian]] [[mathematician]] [[Pál Turán]] in 1941,{{r|turan}} although a [[special case]] of the theorem was stated earlier by Mantel in 1907.{{r|mantel}}
+==Statement==
-==Formal statement==
-:'''Turán's Theorem.''' Let {{mvar|G}} be any graph with {{mvar|n}} vertices, such that {{mvar|G}} is ''K''<sub>''r''+1</sub> -free. Then the number of edges in {{mvar|G}} is at most
+Turán's theorem states that every graph <math>G</math> with <math>n</math> vertices that does not contain <math>K_{r+1}</math> as a subgraph has a number of edges that is at most
 ::<math>\frac{r-1}{r}\cdot\frac{n^2}{2} = \left( 1-\frac{1}{r} \right) \cdot\frac{n^2}{2}.</math>
+The same formula gives the number of edges in the Turán graph <math>T(n,r)</math>, so it is equivalent to state Turán's theorem in the form that, among the <math>n</math>-vertex simple graphs with no <math>(r+1)</math>-cliques, <math>T(n,r)</math> has the maximum number of edges.{{r|az}}
+==Proofs==
-An equivalent formulation is the following:
+{{harvtxt|Aigner|Ziegler|2018}} list five different proofs of Turán's theorem.{{r|az}}
+Turán's original proof uses induction on the number of vertices. Given an <math>n</math>-vertex <math>K_{r+1}</math>-free graph with more than <math>r</math> vertices and a maximal number of edges, the proof finds a clique <math>K_r</math> (which must exist by maximality), removes it, and applies the induction to the remaining <math>(n-r)</math>-vertex subgraph. Each vertex of the remaining subgraph can be adjacent to at most <math>r-1</math> clique vertices, and summing the number <math>(n-r)(r-1)</math> of edges obtained in this way with the inductive number of edges in the <math>(n-r)</math>-vertex subgraph gives the result.{{r|turan|az}}
-:'''Turán's Theorem (Second Formulation).''' Among the {{mvar|n}}-vertex simple graphs with no {{math|(''r'' + 1)}}-cliques, {{math|''T''(''n'', ''r'')}} has the maximum number of edges.
+A different proof by [[Paul Erdős]] finds the maximum-degree vertex <math>v</math> from a <math>K_{r+1}</math>-free graph and uses it to to construct a new graph on the same vertex set by removing edges between any pair of non-neighbors of <math>v</math> and adding edges between all pairs of a neighbor and a non-neighbor. The new graph remains <math>K_{r+1}</math>-free and has at least as many edges. Repeating the same construction recursively on the subgraph of neighbors of <math>v</math> eventually produces a graph in the same form as a Turán graph (a collection of <math>p</math> independent sets, with edges between each two vertices from different independent sets) and a simple calculation shows that the number of edges of this graph is maximized when all independent set sizes are as close to equal as possible.{{r|az|erdos}}
-==Proof==
-Let {{mvar|G}} be an {{mvar|n}}-vertex, simple graph with no {{math|(''r'' + 1)}}-clique and with the maximum number of edges.
+{{harvtxt|Motzkin|Straus|1965}} prove Turán's theorem using the [[probabilistic method]], by seeking a [[discrete probability distribution]] on the vertices of a given <math>K_{r+1}</math>-free graph that maximizes the expected number of edges in a randomly chosen [[induced subgraph]], with each vertex included in the subgraph independently with the given probability. For a distribution with probability <math>p_i</math> for vertex <math>v_i</math>, this expected number is <math>\textstyle\sum_{(v_i,v_j)\in E(G)} p_ip_j</math>. Any such distribution can be modified, by repeatedly shifting probability between pairs of non-adjacent vertices, so that the expected value does not decrease and the only vertices with nonzero probability belong to a clique, from which it follows that the maximum expected value is at most <math>(r-1)/2r</math>. Therefore, the expected value for the uniform distribution, which is exactly the number of edges divided by <math>1/n^2</math>, is also at most <math>(r-1)/2r</math>, and the number of edges itself is at most <math>n^2(r-1)/2r</math>.{{r|az|ms}}
-'''Overview''' We show that an {{mvar|n}}-vertex graph with no {{math|(''r'' + 1)}}-clique and the maximum number of edges must be the Turán graph <math>T(n, r)</math>.  For example, with <math>n = 23</math>, to create the graph with as many edges as possible that contains no triangles, subdivide the vertices into two groups: {{mvar|A}} and {{mvar|B}}, where <math>|A| = 12</math> and <math>|B| = 11</math>.  Put an edge between every vertex in {{mvar|A}} and every vertex in {{mvar|B}} but put no edges within {{mvar|A}} or {{mvar|B}}.  This gives us a total of <math>11\cdot12 = 132 \leq \frac{23^2}{2}\left(1-\frac{1}{2}\right) = 132.25</math>.
+A proof by [[Noga Alon]] and [[Joel Spencer]], from their book ''The Probabilistic Method'', considers a [[random permutation]] of the vertices of a <math>K_{r+1}</math>-free graph, and the largest clique formed by a prefix of this permutation. By calculating the probability that any given vertex will be included, as a function of its degree, the expected size of this clique can be shown to be <math>\textstyle\sum 1/(n-d_i)</math>, where <math>d_i</math> is the degree of vertex <math>v_i</math>. There must exist a clique of at least this size, so <math>\textstyle r\ge\sum 1/(n-d_i)</math>. Some algebraic manipulation of this inequality using the [[Cauchy–Schwarz inequality]] and the [[handshaking lemma]] proves the result.{{r|az}}
-'''Claim 1:''' {{mvar|G}} is a [[complete multipartite graph|complete {{mvar|k}}-partite graph]] with <math>k < r+1</math>.
+Aigner and Ziegler call the final one of their five proofs "the most beautiful of them all"; its origins are unclear. It is based on a lemma that, for a maximal <math>K_{r+1}</math>-free graph, non-adjacency is a [[transitive relation]], for if to the contrary <math>(u,v)</math> and <math>(v,w)</math> were non-adjacent and <math>(u,w)</math> were adjacent one could construct a <math>K_{r+1}</math>-free graph with more edges by deleting one or two of these three vertices and replacing them by copies of one of the remaining vertices. Because non-adjacency is also symmetric and reflexive (no vertex is adjacent to itself), it forms an [[equivalence relation]] whose [[equivalence class]]es give any maximal graph the same form as a Turán graph. As in the second proof, a simple calculation shows that the number of edges is maximized when all independent set sizes are as close to equal as possible.{{r|az}}
-Define a relation over the vertices of {{mvar|G}}:
-:<math>x \sim y </math> if and only if {{mvar|x}} is not adjacent to {{mvar|y}}.
-It suffices to show that <math>\sim</math> is an equivalence relation, as it would partition the vertices of {{mvar|G}} into {{mvar|k}} equivalence classes <math>S_1, \ldots, S_k</math> such that no vertices within the same class are adjacent, and every two vertices from different classes share an edge. Furthermore, as the subgraph induced by choosing exactly one vertex from each equivalence class is a {{mvar|k}}-clique, it follows that <math>k < r+1</math>. Clearly the relation is reflexive (as {{mvar|G}} contains no self-loops), and symmetric, so it suffices to show that the relation is transitive.
-Assume for a contradiction that the relation is not transitive.  In other words, there exist {{mvar|u, v, w}} such that <math>u \sim v</math> and <math>v \sim w</math>, but <math>u \not\sim w</math>.  Letting <math>d(x)</math> denote the degree of a vertex {{mvar|x}}, one of the following must be true:
-Case 1: <math>d(v) < d(u)\text{ or }d(v) < d(w)</math>
-Assume that <math>d(v) < d(u)</math>. Delete vertex {{mvar|v}} and create a copy of vertex {{mvar|u}} (with all of the same neighbors as {{mvar|u}}); call it {{mvar|u′}}. Call this new graph {{mvar|G'}}. Since {{mvar|u}} and {{mvar|u'}} are not adjacent, the largest clique in {{mvar|G'}} can be no bigger than the largest clique in {{mvar|G}}.  However, {{mvar|G'}} contains more edges:
-:<math>|E(G')| = |E(G)| - d(v) + d(u) > |E(G)|.</math>
-Case 2: <math>d(v)\geq d(u)</math> and <math>d(v)\geq d(w)</math>
-Delete vertices {{mvar|u}} and {{mvar|w}} and create two new copies of vertex {{mvar|v}}. As in Case 1, the new graph {{mvar|G'}} cannot contain any {{math|(''r'' + 1)}}-cliques, but does contains more edges:
-:<math>|E(G')| = |E(G)|-(d(u) + d(w) - 1) + 2d(v) \geq |E(G)| + 1.</math>
-Since in either case, a graph {{mvar|G'}} with more edges than {{mvar|G}} can be constructed, which is a contradiction, it follows that  <math>\sim</math> is transitive, and thus an equivalence relation.
-'''Claim 2:'''  The number of edges in a complete {{mvar|k}}-partite graph is maximized when the size of the parts differs by at most one.
-If {{mvar|G}} is a complete {{mvar|k}}-partite graph with parts {{mvar|A}} and {{mvar|B}} and <math>|A| > |B|+1</math>, then we can increase the number of edges in {{mvar|G}} by moving a vertex from part {{mvar|A}} to part {{mvar|B}}. By moving a vertex from part {{mvar|A}} to part {{mvar|B}},  the graph loses <math>|B|</math> edges, but gains <math>|A|-1</math> edges. Thus, it gains at least <math>|A|-1-|B|\geq 1</math> edge. This proves Claim 2.
-'''Claim 3:''' {{mvar|G}} must be a Turán graph.
-The only other possibility is that it has fewer than {{mvar|r}} parts. But in this case one can treat it as a {{mvar|r}}-partite graph in which some of the parts are empty and apply the same reasoning as in claim 2.
 ==Mantel's theorem==
+The special case of Turán's theorem for <math>r=2</math> is Mantel's theorem: The maximum number of edges in an <math>n</math>-vertex [[triangle-free graph]] is <math>\lfloor n^2/4 \rfloor.</math>{{r|mantel}} In other words, one must delete nearly half of the edges in <math>K_n</math> to obtain a triangle-free graph.
-As a special case of Turán's theorem, for ''r'' = 2, one obtains:
-:'''Mantel's Theorem.''' The maximum number of edges in an {{mvar|n}}-vertex [[triangle-free graph]] is <math>\lfloor n^2/4 \rfloor.</math> {{harv|Mantel|1907}}
-In other words, one must delete nearly half of the edges in {{mvar|K<sub>n</sub>}} to obtain a triangle-free graph.
-A strengthened form of Mantel's theorem states that any hamiltonian graph with at least ''n''<sup>2</sup>/4 edges must either be the [[complete bipartite graph]] ''K''<sub>''n''/2,''n''/2</sub> or it must be [[pancyclic graph|pancyclic]]: not only does it contain a triangle, it must also contain cycles of all other possible lengths up to the number of vertices in the graph {{harv|Bondy|1971}}.
+A strengthened form of Mantel's theorem states that any Hamiltonian graph with at least <math>n^2/4</math> edges must either be the [[complete bipartite graph]] <math>K_{n/2,n/2}</math> or it must be [[pancyclic graph|pancyclic]]: not only does it contain a triangle, it must also contain cycles of all other possible lengths up to the number of vertices in the graph.{{r|bondy}}
-Another strengthening of Mantel's theorem states that the edges of every {{mvar|n}}-vertex graph may be covered by at most <math>\lfloor n^2/4 \rfloor</math> [[clique (graph theory)|cliques]] which are either edges or triangles. As a corollary, the [[Intersection number (graph theory)|intersection number]] is at most <math>\lfloor n^2/4 \rfloor</math> {{harv|Erdős|Goodman|Pósa|1966}}.
+Another strengthening of Mantel's theorem states that the edges of every <math>n</math>-vertex graph may be covered by at most <math>\lfloor n^2/4 \rfloor</math> [[clique (graph theory)|cliques]] which are either edges or triangles. As a corollary, the graph's [[Intersection number (graph theory)|intersection number]] (the minimum number of cliques needed to cover all its edges) is at most <math>\lfloor n^2/4 \rfloor</math>.{{r|egp}}
 == See also ==
@@ Line 67: / Line 38: @@
 ==References==
+{{reflist|refs=
-*{{Citation | last1=Aigner | first1=Martin | last2=Ziegler | first2=Günter M. | authorlink2=Günter M. Ziegler | title=[[Proofs from THE BOOK]] | publisher=[[Springer-Verlag]] | location=Berlin, New York | year=1998}}.
-*{{citation
+<ref name=az>{{citation
+ | last1 = Aigner | first1 = Martin | author1-link = Martin Aigner
+ | last2 = Ziegler | first2 = Günter M. | author2-link = Günter M. Ziegler
+ | contribution = Chapter 41: Turán’s graph theorem
+ | doi = 10.1007/978-3-662-57265-8_41
+ | edition = 6th
+ | isbn = 978-3-662-57265-8
+ | pages = 285–289
+ | publisher = Springer-Verlag
+ | title = Proofs from THE BOOK
+ | title-link = Proofs from THE BOOK
+ | year = 2018}}</ref>
+<ref name=bondy>{{citation
  | last = Bondy | first = J. A. | authorlink = John Adrian Bondy
  | doi = 10.1016/0095-8956(71)90016-5
@@ Line 76: / Line 61: @@
  | title = Pancyclic graphs I
  | volume = 11
- | year = 1971}}.
+ | year = 1971}}</ref>
-*{{citation
+<ref name=erdos>{{citation
+ | last = Erdős | first = Pál | authorlink = Paul Erdős
+ | journal = Matematikai Lapok
+ | language = Hungarian
+ | mr = 307975
+ | pages = 249–251
+ | title = Turán Pál gráf tételéről
+ | trans-title = On the graph theorem of Turán
+ | url = https://users.renyi.hu/~p_erdos/1971-27.pdf
+ | volume = 21
+ | year = 1970}}</ref>
+<ref name=egp>{{citation
  | last1 = Erdős | first1 = Paul | authorlink1 = Paul Erdős
  | last2 = Goodman | first2 = A. W. | last3 = Pósa | first3 = Louis | authorlink3=Lajos Pósa (mathematician)
@@ Line 85: / Line 83: @@
  | volume = 18 | issue = 1 | year = 1966 | pages = 106–112
  |mr=0186575
- | doi = 10.4153/CJM-1966-014-3}}.
+ | doi = 10.4153/CJM-1966-014-3}}</ref>
-*{{citation
+<ref name=mantel>{{citation
  | last = Mantel | first = W.
  | journal = Wiskundige Opgaven
@@ Line 92: / Line 91: @@
  | title = Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff)
  | volume = 10
- | year = 1907}}.
+ | year = 1907}}</ref>
-* {{Citation
+<ref name=ms>{{citation
+ | last1 = Motzkin | first1 = T. S. | author1-link = Theodore Motzkin
+ | last2 = Straus | first2 = E. G. | author2-link = Ernst G. Straus
+ | doi = 10.4153/CJM-1965-053-6
+ | journal = [[Canadian Journal of Mathematics]]
+ | mr = 175813
+ | pages = 533–540
+ | title = Maxima for graphs and a new proof of a theorem of Turán
+ | volume = 17
+ | year = 1965}}</ref>
+<ref name=turan>{{Citation
  | last = Turán
  | first = Paul
@@ Line 101: / Line 112: @@
  | volume = 48
  | pages = 436–452
- | language = Hungarian
+ | language = Hungarian}}</ref>
- | postscript = .
- }}
+}}
-*{{Citation | last1=West | first1=Douglas Brent | title=Introduction to Graph Theory | origyear=1996 | publisher=[[Prentice Hall]] | edition=2nd | isbn=978-0-13-014400-3 | year=1999}}.
 {{DEFAULTSORT:Turans theorem}}