- Extremal graph theory
**Extremal graph theory**is a branch ofmathematics .In the narrow sense, extremal graph theory studies the graphs which are "extremal" among graphs with a certain property. There are various meanings for the word "extremal": with the largest number of edges, the largest minimum degree, the smallest diameter, etc. In a broader sense, various other related questions can be included into extremal graph theory. In that case, the term

**extremal graph theory**can encompass a large part ofgraph theory .A typical result in extremal graph theory is

Turán's theorem . It answers the following question. What is the maximum possible number of edges in an undirected graph "G" with "n" vertices which does not contain "K"_{"3"}(three vertices "A", "B", "C" with edges "AB", "AC", "BC"; i.e. a triangle) as a subgraph? Thebipartite graph where the partite sets differ in their size by at most 1, is the only extremal graph with this property. It contains:$leftlfloor\; frac\{n^2\}\{4\}\; ight\; floor$ edges. Similar questions have been studied with various other subgraphs "H" instead of "K"_{"3"}; for instance, theZarankiewicz problem concerns the largest graph that does not contain a fixedcomplete bipartite graph as a subgraph.Turán also found the (unique) largest graph not containing "K"_{"k"}which is named after him, namelyTurán graph . This graph has :$leftlfloor\; frac\{(k-2)\; n^2\}\{2(k-1)\}\; ight\; floor\; =\; leftlfloor\; left(\; 1-\; frac\{1\}\{k-1\}\; ight)\; frac\{n^2\}\{2\}\; ight\; floor$ edges. For "C"_{"4"}, the largest graph on "n" vertices not containing "C"_{"4"}has :$left(frac\{1\}\{2\}+o(1)\; ight)\; n^\{3/2\}$ edges.**ee also***

Ramsey's theorem **References**#

Béla Bollobás . "Extremal Graph Theory". New York: Academic Press, 1978.

# Béla Bollobás. "Modern Graph Theory", chapter 4: Extremal Problems. New York: Springer, 1998.

#

# M. Simonovits, Slides from the Chorin summer school lectures, 2006. [*http://www.renyi.hu/~miki/BerlinG.pdf*]

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Graph theory**— In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and … Wikipedia**Minor (graph theory)**— In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… … Wikipedia**Clique (graph theory)**— A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue … Wikipedia**List of graph theory topics**— This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 … Wikipedia**Extremal length**— In the mathematical theory of conformal and quasiconformal mappings, the extremal length of a collection of curves Gamma is a conformal invariant of Gamma. More specifically, suppose thatD is an open set in the complex plane and Gamma is a… … Wikipedia**Turán graph**— The Turán graph T(13,4) Named after Pál Turán v · … Wikipedia**Triangle-free graph**— In the mathematical area of graph theory, a triangle free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4,… … Wikipedia**Uniquely colorable graph**— In graph theory, a uniquely colorable graph is a k chromatic graph that has only one possible (proper) k coloring up to permutation of the colors. Example 1 . A minimal imperfect graph is a graph in which every subgraph is perfect. The deletion… … Wikipedia**Ramanujan graph**— A Ramanujan graph, named after Srinivasa Ramanujan, is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are excellent spectral expanders.Examples of Ramanujan graphs include the clique,… … Wikipedia**Grötzsch graph**— infobox graph name = Grötzsch graph namesake = Herbert Grötzsch vertices = 11 edges = 20 chromatic number = 4 chromatic index = girth = 4 properties = The Grötzsch graph is a triangle free graph with 11 vertices, 20 edges, and chromatic number 4 … Wikipedia