graph G(V,E) construct an electrical network: d(u)】 d(x) for every edge e Re =1 each vertex u d() d(y) inject d(u)units 2m current flow into u a special vertex v: remove all 2m units current flow from v Lemma: /u∈V,φu,v=Tu,wLecture 23: November 17 23-3 Figure 23.1: Graph as an electrical network Definition 23.5 The e↵ective resistance R(u, v) between two nodes u and v is the potential di↵erence between u and v that is required to send one unit of current from u to v. Now we prove a few useful lemmas about hitting times. Consider first Scenario A, in which we inject d(x) units of current into each node x, and remove all 2m = P x d(x) units of current from node v, where d(x) denotes the degree of x. (See Figure 23.2.) Lemma 23.6 The potential di↵erence ￾u,v between v and any other node u in Scenario A satisfies ￾u,v = Hu,v. Figure 23.2: Scenario A Proof: Consider any vertex u 2 V . Using Kircho↵’s Laws and Ohm’s Law, we have d(u) = X (u,x)2E (current u ! x) (K1) = X (u,x)2E ￾u,x (Ohm) = X (u,x)2E (￾u,v ￾ ￾x,v) (K2) = d(u)￾u,v ￾ X (u,x)2E ￾x,v. Rearranging thus gives ￾u,v =1+ 1 d(u) X (u,x)2E ￾x,v. (23.1) On the other hand, consider the random walk starting from u. Thinking of just the first step of this walk, we see that the hitting time Hu,v satisfies Hu,v =1+ 1 d(u) X (u,x)2E Hx,v. But this is exactly the same system of linear equations as (23.1), satisfied by ￾u,v. Since we know that this system has a unique solution (the potentials are uniquely determined by the current flows), we deduce that Hu,v = ￾u,v 8u, v 2 V. for every edge e : each vertex u : Re = 1 inject d(u) units current flow into u remove all 2m units current flow from v Lemma: 8u 2 V, ￾u,v = ⌧u,v graph G(V,E) construct an electrical network: a special vertex v :