The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+3 votes
135 views

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).
in Graph Theory by Veteran (98.3k points)
edited by | 135 views

1 Answer

+2 votes
Best answer

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.

by Active (4k points)
selected by

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
49,807 questions
54,727 answers
189,302 comments
79,845 users