DescriptionIn this thesis we present two results in Extremal Graph Theory. The first result is a new proof of a conjecture of Bollobas on embedding trees of bounded degree. The second result is a new proof of the Posa conjecture.
Let G=(W,E) be a graph on n vertices having minimum degree at least n/2 + c log(n), where c is a constant. Bela Bollobas conjectured that every tree on n vertices with bounded degree can be embedded into G. We show that this conjecture is true. In fact we show more, that unless G is very close to either the union of two complete graphs on n/2 vertices, or the complement, then a minimum degree of n/2 is sufficient to embed any tree of bounded degree.
The k-th power of C is the graph obtained from C by joining every pair of vertices at a distance at most k in C. In 1962 Posa conjectured that any graph G of order n and minimum degree at least 2n/3 contains the square of a Hamiltonian cycle. The conjecture was proven for n > n_0 by Komlos, Sarkozy and Szemeredi using the Regularity Lemma and Blow-up Lemma. The new proof removes the use of the Regularity Lemma and establishes the Posa conjecture using combinatorial arguments, thus vastly reducing n_0.