Combinatorics and Graph Theory · Problem 5.7.2

Graph Theory — David Guichard

Mathematics — Combinatorics · connectivity

Problem

Suppose a general graph

G

has exactly two odd-degree vertices,

v

and

w

. Let

G'

be the graph created by adding an edge joining

v

w

. Prove that

G'

is connected if and only if

G

is connected.