Does this graph have a Hamilton Path?
Hint
Does this graph have a Eulerian Path?
Hint
If no, where can the fewest amount of edges be added to make one?
Hint
Solutions
1. There is no Hamilton Path. No matter how one attempts to make a Hamilton Path, the path will have to include the the center vertex and doing so will mean that one of the branches it is connected to will be disconnected from the graph.
Hint
Does this graph have a Eulerian Path?
Hint
If no, where can the fewest amount of edges be added to make one?
Hint
Solutions
1. There is no Hamilton Path. No matter how one attempts to make a Hamilton Path, the path will have to include the the center vertex and doing so will mean that one of the branches it is connected to will be disconnected from the graph.
2. There is an Eulerian Path. Since the graph is connected and has no vertex connected to an odd number of edges, there will be an Eulerian Path. One example is:
3. Since there is only no Hamilton Path, we only need to add edges until we find a Hamilton Path. Adding 2 edges, can result in the graph not being disconnected after removing the center vertex, so that there will be multiple ways to make a Hamilton Path. However, adding 1 edge connecting two different "branches" of the graph will give:
Reflection: Problem solving in mathematics is about finding a path that can be replicated to other problems that eventually leads to a solution. This path is abstract thinking and reasoning as much as it is a number of sequential steps to solve for "x" or "y." This problem illustrates what was discussed in the Seven Bridges of Königsberg by Euler. Graph Theory allows mathematicians to model complex relationships and make conclusions about them. Taking a derivative or solving for "x" won't find which vertex in a graph can be removed to disconnect the graph. Instead, clear reasoning about a mathematical structure will find a solution.