Post your solutions to the May 9 In-Class Exercise to this thread.

Best,

Chris

labelling is as above There's 15 edges and 10 vertices

let E = {A,B,C,D,E,F,G,H,I,J} let X = {} let Y = {}

for A: X = {A}; Y = {} for B: X = {A,B}; Y = {} for C: X = {A,B}; Y = {C} for D: X = {A,B,D}; Y = {C} for E: X = {A,B,D}; Y = {C,E} for F: X = {A,B,D,F}; Y = {C,E} for G: X = {A,B,D,F}; Y = {C,E,G} for H: X = {A,B,D,F,H}; Y = {C,E,G} for I: X = {A,B,D,F,H,I}; Y = {C,E,G} for J: X = {A,B,D,F,H,I,J}; Y = {C,E,G}

disjoint edges = {AE,EJ,ED,GB,GJ,GI} X = {A,B,D,F,H,I,J}; Y = {C,E,G} Cut size = 9

Order of vertices: Number the outside points from 1-5 in clockwise order starting from the top Number the inside points from 6-10 in clockwise order starting from the top

Need 15 flips: 0110100011

Graph A: (1,4,6,7,8) Graph B: (2,3,5,9,10)

Cut size = 2

Coin flips = [1, 0, 1, 1, 0, 1, 0, 0, 1, 0]

The vertices are arranged in an order in the clockwise direction

Let the edges be A, B, C, D, E, F, G, H, I, J

Assigning the vertices to either set a, or b

a = [A, C, D, F, I] b = [B, E, G, H, J]

The cut size is 6

After 10 simultaneous online coin flips, we have: A = {1, 2, 5, 6, 7, 8, 9} B = {3, 4, 10}

Hence, cut size is 7, which is within a factor of 2 of m = 15. Hence, MAX-CUT has returned the average case in this instance.

<nowiki> </nowiki>