876 views
Let G be a planar Graph Such that every phase is bordered by exactly 3 edges which of the following can never be value for X(G)

a)2  b)3 C)4 d)none of these

Let G be a planar Graph Such that every phase is bordered by exactly 3 edges

since graph conain odd length cycle, its chromatic no. X(G)>=3

so 2 can never be X(G), hence option a is correct.

Yes option a) is correct 2 is not possible because when a region consist exactly 3 edges means vertices joining them are adjacent and should be colored uniquely. You can also observe this with example below

$\chi (G) \leq \Delta (G) + 1$

1
1,387 views
1 vote