MathDB

A simple graph G of 2014 vertices that satisfies the following conditions at the

Source: 2014 Peru Ibero TST P6

September 16, 2023

combinatorics

Problem Statement

Determine the largest positive integer

k

for which there exists a simple graph

G

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