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).

edited | 135 views

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

1
2