Graph Theory question about Electrical Networks on Bipartite Graphs

Question

How can I find the effective resistance between any two points on a complete bipartite graph $K_{m,n}$? I want to try and identify any equipotential points in order to simplify the problem, but I'm not sure if I'm doing this correctly.

So far I think, if I have two nodes from the same partition of the graph, that I can contract the other partition yielding an effective resistance of $\frac{2}{n}$ where n is the size of the contracted partition.

But when it comes to two vertices which are from different partitions of $K_{m,n}$, I can't seem to figure out how to simplify the problem.

Answer 1

Let $v$ be the vertex in the first ($m$-sized) part of $K_{m,n}$ and let $w$ be the vertex in the second ($n$-sized) part. Say we want to find the effective resistance between $v$ and $w$.

By symmetry, all vertices in the first part other than $v$ have the same voltage potential (or whatever the correct terminology is; I'm a graph theorist, not an electrical engineer), so we can combine them into a single vertex $x$. Similarly, we can combine all vertices in the second part other than $w$ into a single vertex $y$. This gives us a $4$-vertex graph:

This graph is series-parallel. Between $v$ and $y$, we have $n-1$ edges, so the resistance there is $\frac1{n-1}$; between $x$ and $y$, it is $\frac1{(m-1)(n-1)}$; between $x$ and $w$, it is $\frac1{m-1}$. There are two ways to get from $v$ to $w$, so the effective resistance is $$ \frac1{\frac11 + \frac1{\frac1{n-1} + \frac1{(m-1)(n-1)} + \frac1{m-1}}} = \frac1{1 + \frac{(m-1)(n-1)}{m+n-1}} = \frac{m+n-1}{mn}. $$

---

An alternate solution uses the identity that in any graph $G$, we have $$ \sum_{xy \in E(G)} \frac{R_{xy}^{\text{eff}}}{R_{xy}} = |V(G)|-1. $$ In this problem, $R_{xy}=1$ for all edges; $R_{xy}^{\text{eff}}$ is the same constant $r$ for all edges, by symmetry; the number of edges in $K_{m,n}$ is $mn$ and the number of vertices is $m+n$. So we have $$ \sum_{e \in E(G)} r = |V(G)|-1 \implies r = \frac{|V(G)|-1}{|E(G)|} \implies r = \frac{m+n-1}{mn}. $$

---

Third solution: the effective resistance between $v$ and $w$, when $vw$ is an edge of the graph, is the probability that a random walk starting at $v$ ends up at $w$ (when it does) by taking the edge $vw$.

In $K_{m,n}$, this can happen in two ways.

1. The very first step is to go from $v$ to $w$. This happens with probability $\frac1n$.
2. The first step is something else (which happens with probability $1 - \frac1n$). Then, every time we're on the same side as $v$, we're equally likely to be at any of the $m$ vertices. So the probability that the vertex we get to $w$ from is $v$ is $\frac1m$.

Combining these, we get a probability of $$ \frac1n + \left(1 - \frac1n\right)\frac1m = \frac1n + \frac1m - \frac1{nm} = \frac{m+n-1}{mn}. $$