Triangle on six vertices

Task number: 4206

Let \( G \) be a graph on six vertices. Prove that it contains either a triangle or an induced independent set on three vertices.

  • Solution

    Choose any vertex \( v \). By analyzing the cases, we verify that at least one of the following possibilities occurs:

    • The vertex \( v \) has a degree of at least three and some of its neighbors are connected by an edge. Then it contains a triangle.
    • The vertex \( v \) has a degree of at least three and none of its neighbors are connected by an edge. Then these neighbors form an independent set of size at least three.
    • The vertex \( v \) has a degree of no more than two, and some of its non-neighbors are not connected by an edge. It then contains an independent set of size three.
    • The vertex \( v \) has a degree of no more than two, and all of its non-neighbors are connected by an edge. Then these non-neighbors form a complete graph on at least three vertices and a triangle within.
Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email