Let be an undirected graph. Let P(x,y) mean that there
Let G be an undirected graph. Let P(x,y) mean that there is a path from vertex x to vertex y.
∃x,y,z, ~Px,y⋀~P(x,z)⋀~P(y,z) represents that
- A.
G has at least three connected components
- B.
G has exactly three connected components
- C.
G has at most three connected components
- D.
None of these
Attempted by 13 students.
Show answer & explanation
Correct answer: A
The expression ∃x,y,z, ~Px,y⋀~P(x,z)⋀~P(y,z) means there exist three vertices x, y, and z such that no path exists between any pair: x and y, x and z, and y and z.
In an undirected graph, if no path exists between two vertices, they belong to different connected components.
Since no path exists between any pair among x, y, and z, each of these vertices must belong to a distinct connected component.
Therefore, the graph must have at least three connected components.
This does not rule out more than three components, so the statement only guarantees a minimum of three.