An Erdős-Gallai-type theorem for keyrings

Alexander Sidorenko

Published 2017-05-29Version 1

A keyring is a graph obtained by appending $r \geq 1$ leaves to one of the vertices of a circle. We prove that for every $r \leq (k-1)/2$, any graph with average degree more than $k-1$ contains a keyring with $r$ leaves and at least $k$ edges. We also prove the validity of the Erd\H{o}s-S\'{o}s conjecture for some classes of trees.