Suggested languages for you:

Americas

Europe

Q5.

Expert-verified
Found in: Page 332

Geometry

Book edition Student Edition
Author(s) Ray C. Jurgensen, Richard G. Brown, John W. Jurgensen
Pages 227 pages
ISBN 9780395977279

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.

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.

See the step by step solution

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.

Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.