Grinberg-Introduction-Graph-Theory · Problem 2.11

Simple graphs

Mathematics — Graph Theory · connectedness-equivalent-characterization

Problem

Let

G

be a simple graph with

\mathrm{V}(G) \neq \emptyset

. Show that the following two statements are equivalent: • Statement 1: The graph

G

is connected. • Statement 2: For every two nonempty subsets

A

and

B

\mathrm{V}(G)

satisfying

A \cap B = \emptyset

and

A \cup B = \mathrm{V}(G)

, there exist

a \in A

and

b \in B

such that

ab \in \mathrm{E}(G)

. (In other words: Whenever we subdivide the vertex set

\mathrm{V}(G)

G

into two nonempty subsets, there will be at least one edge of

G

connecting a vertex in one subset to a vertex in another.)