Introduction to Graph Theory · Problem 2.11

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · graph-connectedness-characterization

Problem

Let

G

be a simple graph with

V(G) \neq \varnothing

. 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

V(G)

satisfying

A \cap B = \varnothing

and

A \cup B = V(G)

, there exist

a \in A

and

b \in B

such that

ab \in E(G)

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

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.)