Answer to Question #128923 in Discrete Mathematics for usama

Question

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

Answer 1

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.