For a simple (unbiased) random walk on a connected graph with  n  vertices, the cover time (the expected number of steps it takes to visit all vertices) is at most  O ( n  3 ). We consider locally biased random walks, in which the probability of traversing an edge depends on the degrees of its endpoints. We confirm a conjecture of Abdullah, Cooper and Draief [2015] that the min-degree local bias rule ensures a cover time of  O ( n  2 ). For this we formulate and prove the following lemma about spanning trees.   Let  R ( e ) denote for edge e the minimum degree among its two endpoints. We say that a weight function  W  for the edges is feasible if it is nonnegative, dominated by  R  (for every edge  W  ( e ) ≤  R ( e )) and the sum over all edges of the ratios  W ( e )/ R ( e ) equals  n  − 1. For example, in trees  W  ( e ) =  R ( e ), and in regular graphs the sum of edge weights is  d ( n  − 1).    Lemma:  for every feasible  W , the minimum weight spanning tree has total weight  O ( n ).   For regular graphs, a similar lemma was proved by Kahn, Linial, Nisan and Saks [1989].
['Roee David', 'Uriel Feige']
Random walks with the minimum degree local rule have O ( N 2 ) cover time