106 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. ")
edited | 106 views

+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.8k points) 2 10 24
edited
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 (6.8k points) 7 26 92