Graphs, Euler Circuits

Read the book chapters first, then make sure you can answer the questions in the notes. Following that, work on some skills-check problems and exercises. Then take the online quizzes.

Reading

1.1-1.3

Skills Check

1-4, 7-10, 12-14, 18, 19, 21, 23, 25, 27

Exercises

2, 7, 11, 13, 14, 18, 19, 23, 30, 37, 39, 40, 43, 46, 59

Quiz

Take the quiz

1.1

• What is a graph? What are the vertices and edges in a graph?
• Give examples of graphs with 4 vertices and 4 edges.
• Provide at least 3 different examples of real-world scenarios from your experience that you might model using a graph.
• What is a path in a graph? What is a circuit?
• Could we have two distinct edges that both connect the same two vertices?
• Could we have a vertex that is not connected to any other vertex?
• Could we have an edge that does not connect two vertices?
• What circuits do we call Euler circuits?
• Why are we interested in Euler circuits?
• What did you find most interesting about Leonhard Euler?

1.2

• What are the two key questions we would want to ask about Euler circuits? How do they differ?
• What is the valence of a vertex?
• Can two vertices have the same valence?
• Can two vertices have different valences?
• Can a vertex have a valence of 0? What would that mean for it?
• Observe that every edge in a graph contributes 1 point each to two vertices’ valences. With that in mind, what can we say about the sum of all the valences in relation to the number of edges?
• Why can’t we have a graph that has exactly one odd valence?
• When do we say that a graph is connected?
• If all the valences in a graph are positive, why does that not mean that the graph is connected? Provide an example.
• What does the Euler Circuit Theorem say?
• Demonstrate the ECT in some examples.
• Intuitively, why does it make sense that a graph that is not connected cannot have an EC?
• Intuitively, why does it make sense that a graph that has an odd valence cannot have an EC?
• What is the key guiding principle to keep in mind when trying to find an Euler Circuit in a systematic way?

1.3

• Describe the Chinese Postman Problem. What are some real-world examples where it might come up?
• What does eulerizing a graph mean?
• Can we add any kinds of edges when we are trying to “eulerize” a graph? Explain.
• In rectangular networks what systematic method can we follow to eulerize them?