Adding an edge to an extremal \(4\)-cycle-free graph gives two \(4\)-cycles
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
Conjecture
(proposed by Erdös and Simonovits \( ^{[2]}\))
Every graph \( G \) on \(n\) vertices and \(t(n,C_4)+1\) edges contains at least two copies of \(C_4 \) when \(n\) is large.
Rademacher first observed
\( ^{[1]}\) that
every graph on \( n\) vertices and
\( t(n,K_3)+1\) edges contains
at least
\( \lfloor n/2 \rfloor\) triangles.
Similar questions can be asked for a general graph \( H\),
but relatively few results are known for such problems (except for some
trivial cases such as stars or disjoint edges
\( ^{[2]}\)).
Every graph \( G \) on \(n\) vertices and \(t(n,C_4)+1\) edges contains at least two copies of \(C_4 \) when \(n\) is large.
Bibliography | |
---|---|
1 | P. Erdös, On some problems in graph theory, combinatorial analysis and combinatorial number theory, Graph theory and combinatorics (Cambridge, 1983), 1-17, Academic Press, London-New York, 1984. |
2 | P. Erdös and M. Simonovits, Cube-supersaturated graphs and related problems, Progress in graph theory (Waterloo, Ont., 1982), 203-218, Academic Press, Toronto, 1984. |