Grinberg-Introduction-Graph-Theory · Problem 2.12

Simple graphs

Mathematics — Graph Theory · connectedness-two-graphs

Problem

Let

V

be a nonempty finite set. Let

G

and

H

be two simple graphs such that

\mathrm{V}(G) = \mathrm{V}(H) = V

. Assume that for each

u \in V

and

v \in V

, there exists a path from

u

v

G

or a path from

u

v

H

. Prove that at least one of the graphs

G

and

H

is connected.