Euler Path & Circuit 欧拉回路

定义

Euler Path: use every edge exactly once.

Euler Circuit: use every edge exactly once and it must return to the starting vertex.

定理

For undirected graph:

Euler Path: all vertices other than the two endpoints of P must be even vertices.

Euler Circuit: all vertices have even degree

For directed graph:

Questions

Is it possible to only have one odd vertex?

Answer: No. According to the handshaking theorem,

reference:

Euler Circuit