Proving that the effective resistance across an edge in Kn is 2/n.

Question

1. Show that the effective resistance across an edge in K_n is 2/n .
2. Show same thing for two vertices of the complete bipartite graph K_n,m, both of which are in the “right part” with m vertices.

This question was on my Graph Theory final and I wanted to know how to solve it.

I was considering using a theorem from Bollobas's Modern Graph Theory book from chapter 2, but I wasn't quite sure which one would work to give me the simplest solution..

Any help would be greatly appreciated!

Answer 1

If $s,t$ are vertices in $K_n$ with potential $V_s = 1$, $V_t = 0$, then by symmetry $V_a = V_b$ for any vertices $a,b$ other than $s$ and $t$, so the effective resistance does not change if we combine all other vertices into a single vertex $v$.

This leaves us with a multigraph on three vertices $s,t,v$ with one edge between $s$ and $t$, $n-2$ edges between $s$ and $v$, and $n-2$ edges between $v$ and $t$.

By the series-parallel laws, the effective resistance here is $$\frac{1}{1 + \frac1{\frac1{n-2} + \frac1{n-2}}} = \frac1{1 + \frac{n-2}{2}} = \frac 2n.$$

Similarly, if $s,t$ are vertices on the $m$ side of $K_{n,m}$ then we can smash all other vertices on the $m$ side together into a vertex $v$, and smash all vertices on the $n$ side together into a vertex $w$. Also, we can forget $v$, since now it lies on no $s,t$-path. So we have a multigraph on three vertices $s,t,w$ with $n$ edges between $s$ and $w$, and $n$ edges between $s$ and $t$.

By the series-parallel laws, the effective resistance here is $\frac1n + \frac1n = \frac2n$.

Answer 2

You may also use Foster's theorem as I answered in your other question. The effective resistance of any edge (by symmetry) will be equal to $\frac{n-1}{{n\choose 2}}=\frac{2}{n}$.