+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 in Discrete Maths by gbeditor (32,710 points)
reshown Jul 13, 2019 by gbeditor

1 Answer

0 votes

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.


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)