MATH 225N WEEK 4 EXAM PREPARATION PACK 2026 KEY CONCEPTS AND REVISION NOTES

MATH 225N WEEK 4 EXAM PREPARATION PACK
2026 KEY CONCEPTS AND REVISION NOTES

◉ Edges.
Answer: joins two vertices; always end at vertices


◉ vertex.
Answer: end of an edge; or isolated point


◉ Valence.
Answer: number of ends of edges connected to the vertex


◉ isomorphic graphs.
Answer: Show the same information but are drawn differently


◉ path.
Answer: any connected sequence of edges (abcd)


◉ circuit.
Answer: a path that starts and ends at the same vertex (abca)

, ◉ connected graph.
Answer: every pair of vertices is connected by some path


◉ Euler Circuit.
Answer: starts at a vertex, crosses each edge exactly once, and ends
at starting vertex


◉ Euler Theorm : Does this path have an euler circuit?.
Answer: 1. the graph is connected
2. all vertices have even valences


◉ Euler Path.
Answer: covers each edge exactly once, but may not end at starting
vertex


◉ How to tell if a graph has an euler path?.
Answer: If 2 or fewer vertices have odd valences and the graph is
connected
(odd vertices begin and end path)


◉ Postman Problem.
Answer: add edges until every valence is even