euler circuits

Concepts in Math

Course: Math 170
Term: Spring 2026
Institution: Salve Regina University

Urban Services

Chapter 1

Most Efficient Way to Plow Snow

Management Science

  • Definition of Management Science

    • It is an attempt to find the best way to solve problems.

    • Utilizes mathematical methods to identify optimal solutions to management issues.

  • Goal: Find an optimal solution.

  • Optimal Solution: The most favorable outcome in a scenario.

  • Commonly categorized as optimization problems.

What are Optimization Problems?

  • Various sectors (government, business, individuals) pursue optimal results.

  • Examples of Optimization Problems:

    • Finishing a job quickly.

    • Maximizing profits.

    • Minimizing costs.

  • Examples in Urban Services:

    • Ensuring efficiency in:

    • Delivering mail.

    • Removing snow.

    • Checking parking meters.

Euler Circuits

Section 1.1

Examples of Urban Service Challenges

  • Task: Determine an efficient route for a parking-control officer checking parking meters on foot.

    • Importance of Efficient Routes: Helps save money.

Goals of the Parking Control Officer

  1. Cover all sidewalks with parking meters without retracing unnecessary steps.

  2. The route must start and end at the same location.

Graph Representation of the Area

  • Transformation of Map to Graph:

    • The street map is transformed into a graph.

  • Definition of Graph:

    • A graph consists of a finite number of dots (vertices) connected by links (edges).

    • Each edge must connect two different vertices.

  • Key Graph Terminology:

    • Vertex (Vertices): A point on the graph where edges meet.

    • Edge: A link that connects two vertices.

  • Applications of Graphs:

    • Can represent various structures such as:

    • A map of city streets.

    • A social network.

    • Electrical power lines.

    • Airline routes.

Example of Graph Usage

  • Graph Analysis:

    • Given a graph where vertices represent cities and edges represent nonstop airline routes, count:

    • Vertices: 5

    • Edges: 8

Graph Terminology Continued

  • Path: A connected sequence of edges starting and ending at a vertex, described by naming the vertices traveled.

  • Circuit: A specific path that begins and ends at the same vertex.

Distinction Between Paths and Circuits

  • Paths:

    • Can start and end at any vertex using the edges provided.

    • Examples:

    • N-L-B

    • N-M-R-B

  • Circuits:

    • Start and end at the same vertex.

    • Examples:

    • M-R-L-M

    • L-R-B-L

Evaluation of Paths and Circuits

  • Example: Analyzing if a series of edges represents a viable path or circuit:

    • Is N-M-L-R-B a path?

    • Answer: Yes

    • Is N-R-B-L-B a circuit?

    • Answer: No, an edge from N to R does not exist.

Returning to the Initial Example

  • Graph Representation:

    • The map is now represented in graph form, where:

    • Each street intersection is a vertex.

    • Each sidewalk containing meters is an edge.

  • Illustration of Path Formation:

    • Can we create a circuit from the graph?

    • Solution: Yes, it is possible to return to the starting vertex and cover each path efficiently while emphasizing deadheading.

    • Deadheading Definition: In shipping, it refers to a return trip made without a load, resulting in wasted time and resources.

Example of Euler Circuits

  • Definition of Euler Circuit:

    • A circuit that traverses each edge of a graph exactly once, not retracing any steps.

Historical Context of Euler Circuits

  • Leonhard Euler:

    • Lived from 1707 to 1783.

    • Notable Swiss-born mathematician.

    • Regarded as the founder of graph theory.

    • Discovered that certain graphs lack Euler circuits.,

Application of Euler Circuits

  • Problem Analysis:

  • Can we find an Euler Circuit in given graph scenarios?

    • No, if a graph requires retracing edges indicates lack of an Euler circuit.

Importance of Euler Circuits

  • Critical Question: Why are Euler circuits essential?

    • They optimize route efficiency.

  • What if there is no Euler circuit?

    • Alternative strategies are required to minimize deadheading and optimize routes.

Finding Euler Circuits

Section 1.2

Two Key Questions

  1. Is there a calculation method to identify if a graph has an Euler circuit?

  2. Is there an algorithmic approach for quickly finding an Euler circuit?

Foundational Concepts for Euler Circuits

  • Two core concepts:

    • Valence

    • Connectedness

Valence

  • Definition: The number of edges connecting to a vertex, similar to counting the spokes on a wheel hub.

  • Vertex Valences Example:

    • Vertex A: Valence = 4

    • Vertex C: Valence = 0 (not typical in ordinary applications)

    • Note: Assume graphs generally have vertices without a valence of 0.

Valence Evaluations in a Graph

  • Given Graph Example:

    • Vertices A, C, F, D: Valence = 2

    • Vertices B and E: Valence = 4

    • Observation:

    • All vertices have even valence. This is a significant feature to consider.

Connectedness

  • Definition: A graph is connected if there is at least one path between every pair of its vertices.

  • Determining Connectivity:

    • Example: Are two specified graphs connected?

    • Solution: No, as there is no path connecting A to C.

Returning to Euler's Questions

  • Euler's Circuit Theorem:

  1. If graph G is connected and all vertices have even valences, then G has an Euler circuit.

  2. If graph G has an Euler circuit, it must be connected with even valences.

Brief Summary of Euler's Circuit Theorem

  • TLDR Version:

    • Euler circuit exists if the graph has connected and even-valent vertices.

    • If any vertex has an odd valence, an Euler circuit is absent.

  • Graph Evaluation Example:

    • If all eight vertices have valence 2 but not all pairs are connected, then the graph lacks an Euler circuit.

Methods to Find Euler Circuits

  • Without resorting to trial and error:

    • Two Methods:

    1. Trial and Error

    2. Fleury's Algorithm

Fleury’s Algorithm

  • Methodology Steps:

  1. Start at any vertex for finding an Euler circuit or at one of two odd-degree vertices for an Euler path.

  2. Select any edge from the vertex, ensuring deletion of the edge does not cause graph disconnection.

  3. Add the edge to the circuit and remove it from the graph.

  4. Repeat until complete.

Illustration of Fleury’s Algorithm

  • Process Analysis: Original Graph.

    • Choosing edge AD, then deleting AD and moving to D.

    • Edge selections must not disconnect the graph; hence cannot choose DC.

    • Continuation leads to the completion of the circuit.

Evaluation of Example Graphs for Euler Circuits

  • Check for Existence:

    • Is the graph connected? Yes.

    • Are all valences even? Yes.

    • Conclusion: The diagram is confirmed to possess an Euler Circuit.

  • Circuit Construction:

    • Starting and ending at vertex A yields a few Euler Circuit solutions.

    • Example Paths:

    • A-D-E-A-C-E-F-C-B-A

    • A-E-C-A-B-C-F-E-D-A