GATE CSE
First time here? Checkout the FAQ!
x
0 votes
62 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 Active (1.3k points)  
edited by | 62 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.4k 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 (4k points)  
Top Users Jan 2017
  1. Debashish Deka

    9534 Points

  2. sudsho

    5554 Points

  3. Habibkhan

    4878 Points

  4. Bikram

    4774 Points

  5. Vijay Thakur

    4498 Points

  6. Arjun

    4398 Points

  7. saurabh rai

    4236 Points

  8. Sushant Gokhale

    4112 Points

  9. Kapil

    3826 Points

  10. santhoshdevulapally

    3808 Points

Monthly Topper: Rs. 500 gift card

19,355 questions
24,199 answers
53,809 comments
20,368 users