# DM-Graphs-Q15

+1 vote

Let G(V, E) be a simple connected undirected graph with 2 longest paths P1, P2. Starting vertex and ending vertex of P1, P2 are a, b and c, d respectively. x is a vertex which belongs to path P1 but not P2 and y is a vertex which belongs to P2 but not P1.
Which one of the following statements is true?

(A). There can be a path from x to y
(B). There can be a path from a to y
(C). There can be a path from c to x
(D). There exists a vertex which belongs to both P1 and P2 asked Jul 12, 2019
reshown Jul 13, 2019

An undirected graph is connected when it has at least one vertex and there is a path between every pair of vertices. Equivalently, a graph is connected when it has exactly one connected component.

https://en.wikipedia.org/wiki/Connectivity_(graph_theory)

In that case a,b,c,d, x,y all are vertices and the graph is connected hence all must have a path between them since its a connected graph, hence A,B,C should be true as per defination.

I couldn't find any such graph which has a P1 and P2 as such and has no vertex is common so i find D is also true.

Plz comment on the above

answered Jul 13, 2019 by (1,080 points)