The Gateway to Computer Science Excellence
+2 votes
263 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
in Graph Theory by Active (3.1k points) | 263 views
+5

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.

+4

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

 

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,567 answers
195,749 comments
101,708 users