Density Results
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 K3 (three vertices A, B, C with edges AB, AC, BC; i.e. a triangle) as a subgraph? The complete bipartite graph where the partite sets differ in their size by at most 1, is the only extremal graph with this property. It contains
edges. Similar questions have been studied with various other subgraphs H instead of K3; for instance, the Zarankiewicz problem concerns the largest graph that does not contain a fixed complete bipartite graph as a subgraph. Turán also found the (unique) largest graph not containing Kk which is named after him, namely Turán graph. This graph is the complete join of "k-1" independent sets (as equi-sized as possible) and has at most
edges. For C4, the largest graph on n vertices not containing C4 has
edges.
Read more about this topic: Extremal Graph Theory
Famous quotes containing the word results:
“We do not raise our children alone.... Our children are also raised by every peer, institution, and family with which they come in contact. Yet parents today expect to be blamed for whatever results occur with their children, and they expect to do their parenting alone.”
—Richard Louv (20th century)