3.3 Splitting Graphs 20 3.3 Splitting Graphs The MAXCUT problem is the following important algorithmic problem:Given a graph G=(V,E),divide the vertex set into two classes A and B=V\A so that the number of edges going between A and B is maximized.This problem is computationally hard(NP-complete).The following simple result tells us that it is always possible to achieve at least half of the edges going between A and B. 3.3.1 Theorem.Any graph with m edges contains a bipartite subgraph with at least edges. Proof.Let G=(V E).and choose a random subset Tc V by inserting everv vertex into T independently with probability For a given edge e=fu.v},let X denote the indicator variable of the event that eractly one of the vertices of e is in T.Then we have E[XJ=P[(u∈T&vT)or(u生T&v∈T】=子+t=. If X denotes the number of edges having exactly one vertex in T,then EW=于EX=受3.3 Splitting Graphs 20 3.3 Splitting Graphs The MAXCUT problem is the following important algorithmic problem: Given a graph G = (V, E), divide the vertex set into two classes A and B = V \ A so that the number of edges going between A and B is maximized. This problem is computationally hard (NP-complete). The following simple result tells us that it is always possible to achieve at least half of the edges going between A and B. 3.3.1 Theorem. Any graph with m edges contains a bipartite subgraph with at least m 2 edges. Proof. Let G = (V, E), and choose a random subset T ⊆ V by inserting every vertex into T independently with probability 1 2 . For a given edge e = {u, v}, let Xe denote the indicator variable of the event that exactly one of the vertices of e is in T. Then we have E [Xe] = P[(u ∈ T & v /∈ T) or (u /∈ T & v ∈ T)] = 1 4 + 1 4 = 1 2 . If X denotes the number of edges having exactly one vertex in T, then E [X] = X e∈E E [Xe] = m 2 . Thus for some T ⊆ V , there are at least m 2 edges crossing between T and V \T, forming a bipartite graph. ✷