Answer to Question #140766 in Discrete Mathematics for Joseph Se

Question

Eulerian and Hamiltonian Graphs, Weighted Graphs

A. Define the following:

1. Walk
2. Path, Trail
3. Cycle, Circuit

B. What is Eulerian Graph?

C. What is Hamiltonian Graph?

D. Describe how to solve the Konigsberg Problem.

Answer 1

A) 1. A walk is a sequence of vertices and edges of a graph i.e. if we traverse a graph then we get a walk.

2. A path is a trail in which neither vertices nor edges are repeated i.e. if we traverse a graph such that we do not repeat a vertex and nor we repeat an edge. Trail is an open walk in which no edge is repeated.

3. Circuit is traversing a graph such that not an edge is repeated but vertex can be repeated and it is closed also i.e. it is a closed trail. In graph theory, a cycle in a graph is a non-empty trail in which the only repeated vertices are the first and last vertices. 

B) An Eulerian cycle, Eulerian circuit or Euler tour in an undirected graph is a cycle that uses each edge exactly once. If such a cycle exists, the graph is called Eulerian or unicursal. The term "Eulerian graph" is also sometimes used in a weaker sense to denote a graph where every vertex has even degree.

C) A Hamiltonian circuit in a graph is a closed path that visits every vertex inthe graph exactly once. Hamiltonian circuit visits each vertex in a graph exactly once but may repeat edges.

D) Leonard Euler's Solution to the Konigsberg Bridge Problem - Example

Using the Konigsberg problem has his first example Euler shows the following:

                   Number of bridges = 7, Number of bridges plus one = 8

                    Region   Bridges           Times Region Must Appear

                        A            5                                    3

                        B           3                                   2

                        C           3                                   2

                        D           3                                   2

However, 3 + 2 + 2 + 2 = 9, which is more than 8, so the journey is impossible.

Since this example is rather basic, Euler decides to design his own situation with two islands, four rivers, and fifteen bridges. The situation Euler created can be seen in Figure 3 [not available]. Euler now attempts to figure out whether there is a path that allows someone to go over each bridge once and only once. Euler follows the same steps as above, naming the five different regions with capital letters, and creates a table to check it if is possible, like the following:

                        Number of bridges = 15, Number of bridges plus one = 16

                                    Region Bridges     Times Region Must Appear

                                    A*          8                         4

                                    B*          4                         2

                                    C*          4                         2

                                    D            3                         2

                                    E            5                         3

                                    F*          6                         3

In addition, 4 + 2 + 2 + 2 + 3 + 3 = 16, which equals the number of bridges, plus one, which means the journey is, in fact, possible. Since the sum equals the number of bridges plus one, the journey must start in either D or E. Now that Euler knows it is possible to make a journey, all he needs to do is state what the path will be. Euler chooses the path EaFbBcFdAeFfCgAhCiDkAmEnApBoElD, where he includes which bridges are crossed between the letters representing the landmasses. While this information is extraneous, as the exact bridge does not matter in knowing that a journey is possible, it is useful when selecting a path. This is a good example that shows the method which Euler would use when solving any problem of this nature.