I am looking at the paper Graph Clustering and Minimum Cut Trees by Flake et al.
Let $G(V, E)$ be some undirected weighted graph.
Definition. Let $s, t\in V$ be given. Let $(S, T)$ be the minimum cut between $s$ and $t$ which minimizes $|S|$. We call $S$ the community of $s$ with respect to $t$. (It is noted in the paper that indeed the minimality condition guarantees uniqueness of $S$.)
Definition. Given some $\alpha\ge 0$, we define the expanded graph $G_\alpha$ to be $G$ with an additional node $t$, the artificial sink, which is connected to all other nodes in $V$ by edges of constant weight $\alpha$.
Assume now we have chose some $\alpha\ge 0$ and therefore $G_\alpha$. For convenience, I quote the following lemma from the paper.
Lemma 3.9. Let $v_1, v_2\in V$, and $S_1, S_2$ be their communities with respect to $t$ in $G_\alpha$. Then either $S_1$ and $S_2$ are disjoint or one is a subset of the other.
I now want to prove the following statement, which is included implicitly in the text below the lemma:
Statement. Let $v_1\in V$, and $S_1$ be the community of $v_1$ with respect to $t$. Let $v_2\in S_1$ (!), and $S_2$ be the community of $v_2$ with respect to $t$. Then $S_2\subseteq S_1$.
This is necessary to justify the heuristic approach in that section of the paper.
I already see, of course, that in the setting of the above statement, we have either $S_1\subseteq S_2$ or $S_2\subseteq S_1$ by the lemma, as $S_1\cap S_2\neq\emptyset$.
Questions. (i) Why does the statement hold? It looks so easy. Hints instead of full explanations are particularly appreciated! (ii) Is it important that $t$ is an "artificial sink", or would the same results hold when $t$ was any fixed "normal" node?
It appears that the authors are using the proof of Lemma 3.9 instead of its statement. The proof actually justifies the lemma you need:
Lemma 3.9*. Let $v_1, v_2 ∈ V$, and $S_1$, $S_2$ be their communities with respect to $t$ in $G_\alpha$. If $v_1\in S_2$ then $S_1\subseteq S_2$, and if $v_2\in S_1$ then $S_2\subseteq S_1$. Otherwise, $S_1$ and $S_2$ are disjoint.
Although it is not mentioned in the paper, the proof of Lemmas 3.9, 3.9*, and your statement depend on the submodular inequality for cuts. Assume that all edges of $G$ have been given non-negative weights and let $w(S)$ be the total weight of edges having exactly one end in the vertex set $S$. Then
$$w(S\cap T) + w(S\cup T) \leq w(S) + w(T).$$
If we replace $T$ with its complement, we get
$$w(S-T) + w(T-S) \leq w(S)+w(T).$$
To prove the lemmas, apply the above inequalities to $S_1$ and $S_2$ in each of the various cases, using their minimality and the observation that $w(S\cup T)\geq w(S), w(T)$.
(If you haven't seen submodularity before, it is worth proving these inequalities on your own — it's a fairly simple counting argument. Submodularity is a fundamental and ubiquitous tool in structural graph theory, which is why I assume the authors neglected to mention it explicitly.)