Introduction to Graph Theory · Problem 3.10

Multigraphs — Darij Grinberg

Mathematics — Graph Theory · trails-vs-paths-parity

Problem

Let

G

be a loopless multigraph. Recall that a trail (in

G

) means a walk whose edges are distinct (but whose vertices are not necessarily distinct). Let

u

and

v

be two vertices of

G

. As usual, ``trail from

u

v

'' means ``trail that starts at

u

and ends at

v

''. Prove that

\begin{aligned} &(\text{the number of trails from } u \text{ to } v \text{ in } G) \\ &\equiv (\text{the number of paths from } u \text{ to } v \text{ in } G) \pmod{2}. \end{aligned}

[Hint: Try to pair up the non-path trails into pairs. Make sure to prove that this pairing is well-defined (i.e., each non-path trail

\mathbf{t}

has exactly one partner, which is not itself, and that

\mathbf{t}

is the designated partner of its partner!).]