This problem involves directed graphs. A directed graph is a pair (V, E) where V

Question

This problem involves directed graphs. A directed graph is a pair (V, E) where V is a finite set of vertices and E An edge (u, v) means that there is an edge from u to v There can be graphs that have an edge from u to v but not from v to u. V × V is a set of edges. For this problem, there's nothing you need to know about directed graphs other than the above definition. A directed graph G = (V,E) is said to be densely connected if for every pair of distinct vertices u and v in V, there is either an edge from u to v or from v to u, but not both. Here is an example densely connected graph. A Hamiltonian path in a directed graph is a path (the path must respect the directionality of edges, of course) that visits all vertices of the graph and visits them exactly once. For example, in the above graph, d -b -->a -->e is a Hamiltionian path Prove that every densely connected graph with more than one vertex has a Hamiltonian path.

Explanation / Answer

Solution:

The simple graph will contain a hamiltonian path if and only if the sum of degress of each pair of the vertices in the graph is at least n-1.

and sufficient condition for a simple graph G to have hamiltonian path is that the degree of every vertex in G be atleast

n/2 where n is the number of vertices in G.

As per the theorem: In a graph in which if for every pair of distinct vertices u and v in V, there is either an edge from u to v or from v to u, but not both. It will be possible only when degree of each vertex will be at least n/2 for n>1.

hence every densely connected graph with more than one vertex has hamiltonian path.

I hope this helps, please let me know in case of any doubt. Thumbs up if this helped.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.