Explanation: For Directed Acyclic graph, single source shortest distances can be calculated in O(V+E) time. For that purpose Topological Sorting can be used. Topological Sorting of any graph represents a linear ordering of the graph.

Explanation: we know that he Eulerian circuit in a graph G is a circuit that includes all vertices and edges of G. A graph that can have Eulerian circuit, also can have a Eulerian graph.

Explanation: The Eulerian path in a graph say, G is a walk from one vertex to another, that can pass through all vertices of G as well as traverses exactly once every edge of G. Therefore, an Eulerian path can not be a circuit. A Hamiltonian path is a walk that contains every vertex of the graph exactly once. Hence, a Hamiltonian path is not a circuit.

Explanation: A walk in a graph is said to be closed if the starting vertex is the same as the ending vertex, that is v0=vk, it is described as Open otherwise.

Explanation: Suppose in a graph G a trail could be defined as a walk with no repeated edges. Suppose a walk can be defined as efgh. There are no repeated edges so this walk is a trail.

Explanation: In the graph ncfkedn, no edges are repeated in the walk, which makes it a trail and then start and end vertex n is same making it a cycle graph.

Explanation: Let, an n-path complement graph Pn’ is the graph complement of the path graph Pn. Since Pn is self-complementary, P4’ is isomorphic to P4. Now, Pn’ has an edge count = 1⁄2(n-2)(n-1). So, the required edge count is=78.

Explanation: Suppose, the complement G’ of a graph G is known as edge-complement graph which consists of with the same vertex set but whose edge set contains the edges not present in G. The graph sum G+G’ on an n-node graph G is called the complete graph say, Kn.

Explanation: The shortest path will change in the modified graph. Suppose that the shortest path is of weight 21 and has 7 edges and there is another path with 4 edges and total weight 17. Now, the weight of the first shortest path is increased by 7*10 and becomes 21 + 70 and the weight of the second path is increased by 4*10 and becomes 17 + 40. So the shortest path changes to the other path with weight as 57.

Explanation: In BFS due to the least number of edges between two vertices and so if all the edges in a graph are of same weight, then to find the shortest path BFS can be used for efficiency. So we have to split all edges of weight 5 into two edges of weight 2 each and one edge of weight 1. In the worst case, all edges are of weight 1. To split all edges, O(E) operations can be done and so the time complexity becomes which is equal to O(V+E).