Question

True or False: Every graph of 6 vertices must have either an Independent Set of size >= 3 or a clique of size >= 3.

Eithe prove the statement, or provide a counter example.

Answer 1

True.

If the graph has a 3-clique, the statement is satisfied.

If the graph doesn't have a 3-clique, it means that there are no "three vertices mutually connected".

Let's assume we picked two non-adjacent vertices, A and B.

A or B cannot have two neighbors, because in that case, we can pick the two neighbors to form an independent set instead of picking A or B.

Therefore, in the worst case, picking A and B, and eliminating their neighbors, we still have 2 vertices to choose from to form an independent set. This independent set will contain vertices: A, B, and one of the 2 vertices left.

A more general theorem can also prove this, the Turán's theorem

Comments

Please provide a reference to Turan's theorem and the proof outline of the statement in this question using Turan's theorem.

Answer 2

This statement is false. I can take an example to disproof that.

In this graph, any three vertices cannot be a clique. There is no independent set with a size greater than or equal to 3, because each vertex is connected to two adjacent vertices. 

Comments

DEF is a Clique

Answer 3

It is True.

Assume graph has an independent set of size<3.

which means this graph have one group of clique(Is=0) or 2 groups of cliques.

one group of clique: it's 6 vertices all fully connected, so it has a clique of size>=3.

two group of clique: it can be 1,5;2,4 and 3,3, so it has a clique of size>=3.

Answer 4

The given statement is true. For any graph with 6 vertices, it must contain either an Independent Set of size greater than or equal to 3 or a clique of size greater than or equal to 3. This is known as the Ramsey's theorem for small graphs.Consider a graph with 6 vertices.

Case 1: The graph contains an Independent Set of size >= 3: If the graph contains an Independent Set of size 3, then the statement holds true since an Independent Set has no edges between its vertices.

Case 2: The graph does not contain an Independent Set of size >= 3: If there is no Independent Set of size 3, it implies that every set of 3 vertices must contain at least one edge between them. In such a scenario, any set of 3 vertices would form a clique.

Therefore, in the absence of an Independent Set of size >=3, the graph must contain a clique of size >=3.

Thus, in either case, for a graph with 6 vertices, it must contain either an Independent Set of size >= 3 or a clique of size >= 3.