at each step: ·randomly pick a vertex veV and a color c∈[g; change the color of v to c if it is proper; Path Coupling(Bubley-Dyer 1997): there is a coupling (X,)-(X',Y)such that V proper colorings x,ye[g]y that disagree at 1 vertex Eld(X',Y)X=z,Y=y]<(1-a)d(x,y) for some a∈[0,1] Tmix =O(i logn)∀ proper colorings x,y∈[q]V there is a coupling (X,Y)→(X’,Y’) such that • randomly pick a vertex v∊V and a color c∊[q]; • change the color of v to c if it is proper; at each step: for some α∈[0,1] ⌧mix = O ￾ 1 ↵ log n ￾ Path Coupling (Bubley-Dyer 1997): that disagree at 1 vertex E[d(X0 , Y 0 ) | X = x, Y = y]  (1 ￾ ↵)d(x, y)