Bounding the cheeger constant (isoperimetric number)

Question

During my research on Cheeger constant, I've noticed that there are many formulas to represent this constant like: $$ h = \min\frac{|E(X,\bar{X})|}{\min (vol(X),vol(\bar{X}))} $$ or $$ h= \min \frac{|\partial X|}{|X|} $$ where $|\partial X|$ represent the number of edges between the boundary of $X$ and the boundary of $\bar{X}$. In addition to other formulas.

Now, I am interested in the formula presented here to represent the Cheeger constant. It is mentioned that $$ h = \inf \frac{|\partial S|}{|S|} $$ where $|\partial S|$ is the number of edges having precisely one endpoint in the set $S$ and the other endpoint in $\bar{S}$ and for sure this the same definition of $|\partial X|$ in the previous formula.

My Question

In bounding the Cheeger constant in the 2nd page of the same article, the author bounded $|\partial S|$ in the following way:

$$ |\partial S_1|\geq \frac{2|S_1||S_2|}{2(k-1)} $$ which is the number of paths of length 2 between any two vertices in $S_1$ and $S_2$ divided by the number of paths of length 2 in which a given edge can reside.

What I don't understand

Logically, what is the relation between $|\partial S_1|$ and this fraction (the number of paths of length 2 between any two vertices in $S_1$ and $S_2$ divided by the number of paths of length 2 in which a given edge can reside) i.e on what basis he represented the number of edges between two bipartite sets by the number of paths between those sets or how he replaced the edges by the paths!!

Answer 1

There are two assumptions made on the graph where this bound applies:

1. The graph is $k$-regular (which is standard);
2. Between any two vertices $v_1$ and $v_2$, there are exactly two paths of length $2$; this is certainly not true in general.

Given these assumptions, here's how we prove the bound. We take a partition $V = S_1 \cup S_2$, and want to bound $|\partial S_1| = |E(S_1, S_2)|$. Choose any two vertices $v_1 \in S_1$ and $v_2 \in S_2$. Any path of length $2$ from $v_1$ to $v_2$ contains exactly one edge of $\partial S_1$: the path will go from $v_1$ to $w$ to $v_2$ for some third vertex $w$, and either $w \in S_1$ (in which case $(w,v_2)$ is an edge of $\partial S_1$) or $w \in S_2$ (in which case $(v_1, w)$ is an edge of $\partial S_1$).

There are $|S_1||S_2|$ choices of $v_1 \in S_1$ and $v_2 \in S_2$, and two paths from $v_1$ to $v_2$ for each choice, so we get $2|S_1||S_2|$ paths total, each containing an edge of $\partial S_1$.

We divide by $2(k-1)$ because each edge of $\partial S_1$ may end up counted many times. Each edge is counted at most $2(k-1)$ times, because any edge of the graph is contained in at most $2(k-1)$ paths of length $2$: we can extend the edge in one of $2$ directions by one of $k-1$ other neighbors of that endpoint.