Grinberg-Introduction-Graph-Theory · Problem 2.22

Simple graphs

Mathematics — Graph Theory · hamiltonian-cycles-ore-theorem

Problem

(a) Let

G = (V, E)

be a simple graph, and let

u

and

v

be two distinct vertices of

G

that are not adjacent. Let

n = |V|

. Assume that

\deg u + \deg v \geq n

. Let

G' = (V, E \cup \{uv\})

be the simple graph obtained from

G

by adding a new edge

uv

. Assume that

G'

has a hamc. Prove that

G

has a hamc. (b) Does this remain true if we replace ``hamc'' by ``hamp''?