Prove that bar G contains a triangle Prove that If G doesn't contain a triangle then bar G contains one G is a graph of order at least 6, and dG(v)>=3 where v is a vertex of G

assupecoitteem81

assupecoitteem81

Answered question

2022-11-11

Prove that G ¯ contains a triangle
Prove that If G doesn't contain a triangle then G ¯ contains one
G is a graph of order at least 6, and d G ( v ) 3 where v is a vertex of G
Any hints ?

Answer & Explanation

lelestalis80d

lelestalis80d

Beginner2022-11-12Added 23 answers

Assuming G is simple, then the set N(v) (neighbours of v) is an independent set of G since G has no triangles. Therefore G ¯ has a triangle. In fact, any three vertices of N(v) will make a triangle in G ¯ since | N ( v ) | 3

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?