Problem

Source: 2014 Peru Ibero TST P6

Tags: combinatorics



Determine the largest positive integer $k$ for which there exists a simple graph $G$ of $2014$ vertices that simultaneously satisfies the following conditions: $a)$ $G$ does not contain triangles $b)$ For each $i$ between $1$ and $k$, inclusive, at least one vertex of $G$ has degree $i$ $c)$ No vertex of $G$ has a degree greater than $k$