Contents Online

# Journal of Combinatorics

## Volume 7 (2016)

### Number 2–3

Guest editors: Rong Luo and Cun-Quan Zhang

### The Erdős–Sós conjecture for spiders of four legs

Pages: 271 – 283

DOI: https://dx.doi.org/10.4310/JOC.2016.v7.n2.a4

#### Authors

#### Abstract

The Erdős–Sós Conjecture states that if $G$ is a graph with average degree more than $k-1$, then $G$ contains every tree of $k$ edges. A special case of the conjecture is the well-known Erdős–Gallai theorem: if $G$ is a graph with average degree more than $k-1$, then $G$ contains a path of $k$ edges. A spider is a tree with at most one vertex of degree more than $2$, called the center of the spider (if no vertex of degree more than two, then any vertex can be the center). A leg of a spider is a path from the center to a vertex of degree $1$. Thus, a path can be regarded as a spider of 1 or 2 legs. In this paper, we prove that if $G$ is a graph with average degree more than $k-1$, then $G$ contains every spider of 4 legs.

#### Keywords

Erdős–Sós Conjecture, trees, spiders

Published 23 February 2016