Introduction to Graph Theory · Problem 2.5

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · odd-edges-parity

Problem

Let

G = (V, E)

be a simple graph. An edge

e = \{u, v\}

G

will be called odd if the number

\deg u + \deg v

is odd. Prove that the number of odd edges of

G

is even. [Hint: There are several solutions. One uses modular arithmetic and (in particular) the congruence

m^2 \equiv m \bmod 2

for every integer

m

. Other solutions use nothing but common sense.]