Task list filter?

Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.

Task rankings

Difficulty level

Task tags

Task type
«
«
«

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