GATE CSE
First time here? Checkout the FAQ!
x
0 votes
78 views
Let G be a planar graph such that every face is bordered by exactly 3 edges.Which of the following can never be the value for χ(G) ? (where χ(G) is the chromatic number of G)

a)  2

b)  3

c)  4

d)  None of these

PS : (Explain: "every face is bordered by exactly 3 edges. ")
asked in Graph Theory by Loyal (3.1k points)  
edited by | 78 views

2 Answers

+1 vote

I think answer should be (A) because K2 require 2 colors and is not bounded by three edges but Krequire 3 colors, and K4 require 4 colors to color them and both of them are planar graphs and are bounded by exactly 3 edges. Moreover, every face is bordered by exactly three edges means that every REGION formed within the graph must have exactly three edges surrounding them. Have a look at the graphs, every region within graph K3 and K4 are bounded by exactly three edges but K2 is not.

answered by Active (1.5k points)  
edited by
0 votes
as it mentions it's planar and every face is bounded by exactly three edges so the only possibility we have K3 which has chromatic number X(G) =3
answered by Loyal (4.8k points)  
Top Users Feb 2017
  1. Arjun

    5278 Points

  2. Bikram

    4230 Points

  3. Habibkhan

    3942 Points

  4. Aboveallplayer

    3086 Points

  5. Debashish Deka

    2378 Points

  6. sriv_shubham

    2308 Points

  7. Smriti012

    2236 Points

  8. Arnabi

    2008 Points

  9. sh!va

    1672 Points

  10. mcjoshi

    1660 Points

Monthly Topper: Rs. 500 gift card

20,857 questions
26,009 answers
59,671 comments
22,107 users