Solutions and Hints for some of the Exercises

3.1 For

A

⊆

V

(

G

)

$$A \subseteq V(G)$$

let f(A) be the number of edges between A and

V

(

G

)

∕

A

$$ V(G)/A $$

. Let A be such that f(A) is maximal. No vertex

ν

∈

A

$$\nu \in A$$

has more neighbors in A than in V(G)\A as we would have f

(

A

−

ν

)

>

A

$$(A-\nu) > A$$

.