# Questions tagged [extremal-graph-theory]

The study of maximal or minimal graphs satisfying certain properties.

155 questions
Filter by
Sorted by
Tagged with
46 views

### Do sparse graphs contain regular pairs?

A corollary of the Szemeredi Regularity Lemma says that dense graphs contain linear sized $\varepsilon$-regular bipartite subgraphs whose density is similar to that of the parent graph. Could one make ...
51 views

### Sum related to Goodman's Formula

Suppose I have a (improper) 2-coloring of $E(K_n)$. Define the graph of all red edges to be $G$ and the graph of all blue edges to be $G'$. Then Goodman's formula says that the total number of ...
53 views

### Which graphs $G$ in which any circle is an edge separator maximize $||G||$ for fixed |G|?

Questions Is my solution to the following exercise correct? The exercise gives the following hint: Consider the complement of a spanning tree. How would you come up with that hint yourself? Do you ...
35 views

31 views

### Largest Independent Sets in Triangle Free Graphs

We know that in a triangle free graph, the set of neighbours for a vertex forms an independent set. One can show that the order of the largest independent set in a graph must be larger than (or equal ...