Take 5 nodes & 8 edges, Draw any Directed graph (Take help from book, but DO NOT copy paste any graph from examples or exercise.) a) Determine whether the given graph has Hamilton circuit, if it does, find such circuit. b) If not, provide the reason
The Answer to the Question
is below this banner.
Here's the Solution to this Question
Here is a graph with 5 nodes and 8 edges. It is directed. Three numbers near every node indicate a) total number of connection with this vertex, b) number of in-coming paths (with +), c) number of out-coming paths (with -).
All complete directed graphs with two vertices have Hamiltonian path. We can consider given graph, at first, as a graph with 2 vertices and then add vertices one by one. Since the graph is connected and every vertex has as in-coming as out-coming paths, the Hamiltonian circuit exists. It is shown in the picture with the green line.