8

Part of 2001 239 Open Mathematical Olympiad

Problems(1)

throwing out any vertex there is a n-clique prove that there is a n+1-clique

Source: 239 2001 J8

In a graph with

2n-1

vertices throwing out any vertex the remaining graph has a complete subgraph with

n

vertices. Prove that the initial graph has a complete subgraph with

n+1

graph theorycombinatorics