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$ vertices.
Problem
Source: 239 2001 J8
Tags: graph theory, combinatorics
VicKmath7
25.06.2021 14:25
Let's bump this. Solution?
lahmacun
25.06.2021 15:49
this is wrong for n=1 right? by taking an empty graph with 3 vertices. This also fails for n=2. take 2 segments and one isolated vertex
dgrozev
28.06.2021 10:26
lahmacun wrote: this is wrong for n=1 right? by taking an empty graph with 3 vertices. This also fails for n=2. take 2 segments and one isolated vertex Two segments and one isolated vertex, then you mean $n=3\,,\,(2\cdot 3-1=5).$ So, in this case after removing any vertex there should remain a triangle. That is, your "counterexample" fails. I think the statement is true.
hydo2332
29.06.2021 03:43
Where is this problem from? [
lahmacun
29.06.2021 21:07
hydo2332 wrote: Where is this problem from? [ From "239 2001 J8", I suppose it is from an old Saint-Petersburg olympiad