GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
172 views

The number of colours required to properly colour the vertices of every planer graph is

  1. 2
  2. 3
  3. 4
  4. 5
asked in Graph Theory by Veteran (75.6k points)   | 172 views

2 Answers

+2 votes
Best answer

According to the 4-color theorem states that the vertices of every planar graph can be colored with at most 4 colors so that no two adjacent vertices receive the same color.

 

Hence,Option(C)4 is the correct choice

answered by Veteran (29.3k points)  
selected by
0 votes
acc. to 4-color theorem 4 colours are needed to color any simple graph

https://en.wikipedia.org/wiki/Four_color_theorem
answered by Veteran (40.1k points)  
Top Users Feb 2017
  1. Arjun

    5166 Points

  2. Bikram

    4204 Points

  3. Habibkhan

    3748 Points

  4. Aboveallplayer

    2986 Points

  5. sriv_shubham

    2298 Points

  6. Debashish Deka

    2234 Points

  7. Smriti012

    2142 Points

  8. Arnabi

    1998 Points

  9. mcjoshi

    1626 Points

  10. sh!va

    1552 Points

Monthly Topper: Rs. 500 gift card

20,815 questions
25,974 answers
59,606 comments
22,025 users