Answer true or false with justification Answer true or false

Answer true or false, with justification:

Answer true or false, with justification: If an undirected graph has exactly two vertices of odd degree then there must be a path between those two vertices. If an undirected graph G has exactly three vertices of odd degree then G must have an Eulerian circuit. If a connected, undirected graph has two longest simple paths, P and Q, then P and Q must share a vertex.

Solution

(a) TRUE

because In an undirected graph G, tw0 vertices u and v are called connected if G contains a path from u to v. Otherwise, they are called disconnected.

(b) FALSE

because Every vertex of this graph has an even degree, therefore this is an Eulerian circuit as it has 3 verices of add degree

(c) TRUE

yes, p and q must share a vertex.

To tell whether there is a path between two vertices or not is efficient, such as DFS or BFS, it will done within O(V+E). The path should be simple path, i.e with no repeated vertex. It is not necessarily the shortest path.

I HOPE YOU GET MY ANSWERS. have a great time :)