Definition 3.2
(Edge expansion)
.
The
(edge) expansion
of a cut
(
S
,
V
∖
S
)
is defined as
Φ
(
S
,
V
∖
S
)
:
=
max
{
Φ
(
S
)
,
Φ
(
V
∖
S
)
}
=
e
(
S
,
V
∖
S
)
d
min
{
|
S
|
,
|
V
∖
|
}
.