171
Let cut(B, B) be any cut where all version of each node are in the same group. Thus,
cut(B, B) ≤











∑
i∈B
c
∑
j=1
d i j
∑
i∈B
c
∑
j=1
d i j
and vol(B) = ∑
i∈B
c
∑
j=1
t i j = (2c − 1) ∑
i∈B
c
∑
j=1
d i j ,
vol(B) = ∑
i∈B
c
∑
j=1
t i j = (2c − 1) ∑
i∈B
c
∑
j=1
d i j .
Thus, NCut(B, B) =
cut(B, B)
vol(B)
+
cut(B, B)
vol(B)
≤
2
2c − 1
.
Since the NCut(A, A) is the minimum,
NCut(A, A) =
cut(A, A) ∗ vol(V )
vol(A)vol(A)
≤
2
2c − 1
,
vol(V ) ≥ 2(2c − 1)(d Ax + d Ax )
=⇒ (2c − 1)
2 cut(A, A)(d Ax + d Ax ) ≤ vol(A)vol(A).
(B.7)
(B.5) implies
vol(A)vol(A)(kd Ax + (k − 1)d Ax ) ≤ cut(A, A)
vol(A)
kd Ax + (c + k − 1)d Ax
− vol(A)
kd Ax + (c + k − 1)d Ax
+
kd Ax + (c + k − 1)d Ax
2
.
Similarly, (B.6) implies
vol(A)vol(A)(kd Ax + (k − 1)d Ax ) ≤ cut(A, A)
− vol(A)
kd Ax + (c + k − 1)d Ax
+ vol(A)
kd Ax + (c + k − 1)d Ax
+
kd Ax + (c + k − 1)d Ax
2
.