GATE CSE
First time here? Checkout the FAQ!
x
0 votes
94 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.3k points)  
edited by | 94 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.6k 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 Boss (6k points)  

Related questions



Top Users Aug 2017
  1. Bikram

    5276 Points

  2. ABKUNDAN

    4730 Points

  3. akash.dinkar12

    3530 Points

  4. manu00x

    3492 Points

  5. rahul sharma 5

    3188 Points

  6. makhdoom ghaya

    2700 Points

  7. just_bhavana

    2432 Points

  8. stblue

    2244 Points

  9. Tesla!

    2090 Points

  10. pawan kumarln

    1876 Points


25,075 questions
32,231 answers
75,118 comments
30,240 users