Eulerian Circuits Flashcards
1
Q
What is a trail?
A
A walk with no repeated edges
2
Q
What is a circuit?
A
A trail that starts and ends on the same vertex
3
Q
When is a circuit Eulerian?
A
If it contains every edge in the multigraph (can have multiple connections between a pair of vertices)
4
Q
When is a multigraph Eulerian? Also a multigraph is Eulerian iff…
A
When it contains an Eulerian circuit. Iff it is connected and every vertex has even degree.
5
Q
Fill in these 3 equivalent statements:
-G has an ___ ___ starting at v and ending at w
-G+vw has an ___ ___
-G is ___, both v and w have ___ degree, and every other vertex has ___ degree.
A
