The Erdös-Sós conjecture for graphs without \(C_ 4\) (Q1362105)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The Erdös-Sós conjecture for graphs without \(C_ 4\) |
scientific article |
Statements
The Erdös-Sós conjecture for graphs without \(C_ 4\) (English)
0 references
12 August 1997
0 references
In 1963, P. Erdös and V. T. Sós conjectured that every graph \(G=(V,E)\) with \(|E|\geq {1\over 2} |V|(k-1)\) contains every tree \(T\) of size \(k\). This paper proves the conjecture for the case that \(G\) does not contain the cycle \(C_4\).
0 references
subgraphs
0 references
tree
0 references
