Q5. - Geometry

Question

The number of odd vertices will tell you whether or not a network can be   traced without backtracking. Do you see how? If not, read on.

Tell why it is impossible to walk across the seven bridges of Koenigsberg  without   crossing any bridge more than once.    

Step-by-Step Solution

Answer

It is impossible to walk along 7 bridges in a Koenigsberg problem because there are more than 2 odd vertices which cannot be traced without backtracking.

Step 1. Given information:

Koenigsberg bridge problem.

Step 2. Concept use.

A point is called a vertex.

A line is called an edge.

The number edges that lead to a vertex is called the degree of the vertex.

A route around a graph that visits every vertex once is called a simple path.

A route around a graph that visits every edge once is called an Euler path.

Step 3. Applying the concept.

A point is called a vertex.

A line is called an edge.

The number edges that lead to a vertex is called the degree of the vertex.

A route around a graph that visits every vertex once is called a simple path.

A route around a graph that visits every edge once is called an Euler path.

In an Euler path, the number of vertices of odd degree must be either zero or two.

For the Koenigsberg problem, consider the simplified figure of the bridge in the form of a graph: 

Vertices B, C and D have degree 3 and vertex A has degree 5, so this graph has four vertices of odd degree. So, it does not have an Euler path.

Therefore, the Koenigsberg problem is impossible to solve without backtracking.