Log In
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
27 votes

The minimum number of colours required to colour the following graph, such that no two adjacent vertices are assigned the same color, is

  1. $2$
  2. $3$
  3. $4$
  4. $5$
in Graph Theory
edited by

graph is planar so we can directly say it requires not more than 4 color

this graph has also odd length cycle for that 3 color requires

also this graph has even length cycle for that 2 color 

but i have a doubt here :

if graph is very complex and if both the even and odd length cycle appears as well as planar solution then whts the correct aproach to find color requirement in graph 

same situation with this

@Bikram sir which approach ?pls help

The chromatic number of a planar graph is no more than four.

We can use this approach here.

as it is maximum 4 , then 4 colors require for complex kind of graphs where both the even and odd length cycle appears as well as planar solution ..

I am getting answer as 3. Please let me know where I am getting wrong..!!Please let me know where i am getting wrong. !!

Two adjacent vertex have got same color (C1)

6 Answers

30 votes
Best answer

$4$ colors are required to color the graph in the prescribed way.

answer = option C

edited by
Practical approach :)
Here we also need to prove that the given graph can't be colored with less than 4 colors.

As it consists cycle with odd vertices it requires at least 3 colors.

But if you try to color them with 3 colors it is not possible to color them with 3 colors.

More ever any planar graph can be colored with 4 colors (Four color theorem).

This might help ...


If dmax is the maximum degree of a vertex in a graph then the chromatic number of G

 k(G) $\leq$ dmax +1

This upper bound can be improved by 1 if the graph G has no complete graph of dmax +1 vertices

so in this case K(G)$\leq$dmax

Since, in this graph dmax=4, atmost 4 colors are needed to color this graph so first eliminate option (d).

any given graph is there any tricks to find whether the graph is planar or not ??
So we know four color theorem which say any planar graph will be 4 colorable. So this graph is planar so max color required will be 4. Now to strect it you take 3 color and try to color every vertices and you will find definetely 3 is not enough in here so answer is 4.
6 votes

Ans C 

3 votes
note:-The max degree of the vertex is 4 so we need atmost 4 colours to colour the graph

answer is C) 4 only

edited by

This is not a correct theorem/result.Counter ex: Degree of every vertex in Graph K5 is 4 (max degree is 4) but we need 5 colors to color the graph.

correct theorem: If every vertex in G has degree at most d then G admits a vertex coloring using d+1 colors. 

0 votes
4 colors
0 votes
Since the graph is planar graph it is 4 colorable.
–5 votes
The max degree of the vertex is 4 so we need atleast 5 colours to colour the graph
1 flag:
✌ Edit necessary (manish_pal_sunny “wrong answer”)
4 colours are enough here !
It is a planar graph so we need only 4 colour.

 Theorem: If every vertex in G has degree at most d then G admits a vertex coloring using d+1 colors. 

But here d+1 is not the min value.


Related questions

56 votes
5 answers
How many graphs on $n$ labeled vertices exist which have at least $\frac{(n^2 - 3n)}{ 2}$ edges ? $^{\left(\frac{n^2-n}{2}\right)}C_{\left(\frac{n^2-3n} {2}\right)}$ $^{{\large\sum\limits_{k=0}^{\left (\frac{n^2-3n}{2} \right )}}.\left(n^2-n\right)}C_k\\$ $^{\left(\frac{n^2-n}{2}\right)}C_n\\$ $^{{\large\sum\limits_{k=0}^n}.\left(\frac{n^2-n}{2}\right)}C_k$
asked Sep 19, 2014 in Graph Theory Kathleen 7.3k views
26 votes
3 answers
The following finite state machine accepts all those binary strings in which the number of $1$’s and $0$’s are respectively: divisible by $3$ and $2$ odd and even even and odd divisible by $2$ and $3$
asked Sep 19, 2014 in Theory of Computation Kathleen 3.2k views
17 votes
4 answers
Let $A = 1111 1010$ and $B = 0000 1010$ be two $8-bit$ $2’s$ complement numbers. Their product in $2’s$ complement is $1100 0100$ $1001 1100$ $1010 0101$ $1101 0101$
asked Sep 19, 2014 in Digital Logic Kathleen 8.4k views
34 votes
4 answers
Two matrices $M_1$ and $M_2$ are to be stored in arrays $A$ and $B$ respectively. Each array can be stored either in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to compute $M_1 \times M_2$ will be best if ... is in column-major order best if both are in row-major order best if both are in column-major order independent of the storage scheme
asked Sep 19, 2014 in Algorithms Kathleen 5.5k views