Introduction to Graph Theory · Problem 2.12

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · two-graphs-connectedness

Problem

Let

V

be a nonempty finite set. Let

G

and

H

be two simple graphs such that

V(G) = 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.