edited by
569 views
3 votes
3 votes

Suppose each edge of an undirected graph is coloured using one of three colours — red, blue or green. Consider the following property of such graphs: if any vertex is the endpoint of a red coloured edge, then it is either an endpoint of a blue coloured edge or not an endpoint of any green coloured edge. If a graph $G$ does not satisfy this property, which of the following statements about $G$ are valid?

  1. There is a red coloured edge.
  2. Any vertex that is the endpoint of a red coloured edge is also the endpoint of a green coloured edge.
  3. There is a vertex that is not an endpoint of any blue coloured edge but is an endpoint of a green coloured edge and a red coloured edge.
  4. (A) and (C).
edited by

2 Answers

Best answer
2 votes
2 votes

To check the validity of option B :-

Consider a graph $G$ with vertex set $V = \{1, 2, 3\}$ and edge between 1 & 2 is Red, 2 & 3 is Green & 1 & 3 is Red. Here vertex $3$ causes $G$ to violate the property given in the problem statement, but vertex 2 is not obeying option B.

To check the validity of option C:-

Let $V_R$ denotes the endpoint of a red colored edge, $V_B$ denotes endpoint of a blue colored edge and $V_G$ denotes the endpoint of a green colored edge

The given property $P4 in the problem statement can be expressed as

$\forall V [ V_R \Rightarrow V_B \vee \neg V_G]$

i.e., $\forall V [ \neg V_R \vee V_B \vee \neg V_G]$

If a graph $G$ does not satisfy the above property, then it becomes

$ \neg \forall V[\neg V_R \vee V_B \vee \neg V_G] = \exists V [V_R \wedge \neg V_B \wedge  V_G]$

This is the statement in option C.

Since, option C implies option A

 D is the correct option.

selected by
Answer:

Related questions

16 votes
16 votes
2 answers
1
go_editor asked May 27, 2016
2,166 views
An undirected graph has $10$ vertices labelled $1, 2,\dots , 10$ and $37$ edges. Vertices $1, 3, 5, 7, 9$ have degree $8$ and vertices $2, 4, 6, 8$ have degree $7.$ What ...
43 votes
43 votes
4 answers
3
Akash Kanase asked Feb 12, 2016
15,316 views
The minimum number of colours that is sufficient to vertex-colour any planar graph is ________.