# Some properties and characterizations of connected graphons

Federica Garin

► To cite this version:

Federica Garin. Some properties and characterizations of connected graphons. 2025. hal-05342466

HAL Id: hal-05342466

https://inria.hal.science/hal-05342466v1

Preprint submitted on 2 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Some properties and characterizations of connected graphons

Federica Garin

**Abstract**— This paper studies the connectedness of graphons. It highlights that connectedness is related to some spectral property of the graphon-Laplacian operator, which is important for convergence of consensus and other diffusion-based dynamics on large-scale networks. Some equivalent characterizations of connectedness are given, and some subtleties in their definition are discussed through examples.

I. INTRODUCTION

Graphons are a notion of continuous limit of large dense
graphs, as well as a description of a family of random
graphs [1]. They have gained increasing attention in the study
of large-scale network systems, with works on consensus [2],
[3], random walks [4], opinion dynamics [5], [6], synchro-
nization [7], [8], distributed optimization [9], game theory
[10], [11], controllability analysis [12] and control design
[13], [14].

For finite graphs, a well-known result in spectral graph
theory is the fact that an undirected graph is connected if
and only if the dimension of the kernel of its Laplacian
matrix is one. This result plays a crucial role in the proofs of
convergence of several Laplacian-based consensus, opinion
dynamics and synchronization algorithms (also known as
diffusively coupled dynamics). The goal of this paper is to
shed light on the extension of this result to graphons, sum-
marizing some results from recent literature and presenting
some novel results (Prop. 4, one of the two characterizations
in Thm. 2, Thm. 3), together with some examples that clarify
some subtleties involved in the characterizations of graphon
connectedness. These results are key to consensus and syn-
chronization of large-scale network systems described by
graphons, see in particular [2], [3], [5], [9].

II. GRAPHON CONNECTEDNESS AND
GRAPHON-LAPLACIAN SPECTRUM

A. *Connected graphons*

A graphon is a symmetric measurable function $W : I^2 \rightarrow I$, where $I = [0, 1]$.

The following is the classical definition of a connected
graphon, see e.g. [1].

*Definition 1:* A graphon *W* is connected if for all *A* ⊆ *I*
with Lebesgue measure *μ*(*A*) ∈ (0, 1),

$$
\int_{A \times A^c} W(x, y) \, dx \, dy \neq 0,
$$

where $A^c$ denotes the complement set $A^c = I \setminus A$. $\square$

<figure><img src="image_2.png" /></figure>

This work was partly supported by the French National Research Agency through grant COCOON ANR-22-CE48-0011.

F. Garin is with Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, GIPSA-Lab, 38000 Grenoble, France (e-mail: federica.garin@inria.fr).

Since $W(x, y) \ge 0$ for all $x, y$, $\int_{A \times A^c} W(x, y) \, dx \, dy = 0$ if and only if $W = 0$ almost everywhere (a.e.) on $A \times A^c$. With this in mind, the definition of a connected graphon is analogous to the fact that a graph is connected if and only if you cannot separate its vertex set $V$ into two non-empty subsets $A, V \setminus A$ such that there is no edge between $A$ and $V \setminus A$. We will see in Section III how some characterizations of connected graphons can be formulated, that are nearer to the usual definition for graphs (a graph is connected if there is a path from every vertex to every other vertex). In Subsection II-B, instead, we will clarify the relation between graphon connectedness and properties of the spectrum of the graphon Laplacian operator.

It is clear from Definition 1 that the property of being
connected is invariant under changes over a zero-measure
set: if $W(x, y) = \tilde{W}(x, y)$ a.e., then $W$ and $\tilde{W}$ are either
both connected or both not connected. This is convenient,
since we are interested in operators (defined in Subsect. II-
B) which involve the integral of $W$ and are hence unchanged
when $W$ is modified over a zero-measure set.

It is also easy to show that the property of being connected
is invariant under invertible measure-preserving transforma-
tions, which are the analogous of graph isomorphisms (re-
labelling of the graph vertices). Let $\varphi : I \to I$ be a measure-
preserving map, i.e., $\varphi$ is a measurable function such that
for any measurable set $A \subseteq I$ we have $\mu(\varphi^{-1}(A)) = \mu(A)$.
Define $W^{\varphi}(x, y) = W(\varphi(x), \varphi(y))$.

Notice that $W^\varphi$ connected implies $W$ connected. Indeed, we can show that $W$ not connected implies $W^\varphi$ not connected, as follows. Notice that $(\varphi^{-1}(A))^c = \varphi^{-1}(A^c)$ (by definition, both are the set of $x \in I$ such that $\varphi(x) \notin A$), and $\mu(A) \in (0, 1)$ if and only if $\mu(\varphi^{-1}(A)) \in (0, 1)$ thanks to $\varphi$ being measure-preserving. If $W$ is not connected, $W = 0$ a.e. $A \times A^c$ for some $A$ with $\mu(A) \in (0, 1)$; this implies that $W^\varphi = 0$ a.e. $\varphi^{-1}(A) \times \varphi^{-1}(A^c) = \varphi^{-1}(A) \times (\varphi^{-1}(A))^c$, and hence $W^\varphi$ is not connected.

If $\varphi$ is invertible, then also the converse is true. Indeed, the
inverse of a measure-preserving map is measure-preserving,
and so we can apply the above argument using $\varphi^{-1}$.

Two graphons $V, W$ are *isomorphic up to a null set* [1, Sect. 7.3] if there is an invertible measure preserving map $\varphi : I \to I$ such that $V^\varphi = W$ a.e.. When graphons $V, W$ are isomorphic up to a null set, $V$ is connected if and only if $W$ is connected (as shown above).

A weaker notion of graphon isomorphism plays a crucial
role when studying convergence of sequences of graphs of
increasing size to a graphon. The classical definition of
weak isomorphism [1, Sect. 7.3] involves subgraph densities
and is beyond the scope of this paper, but the following characterization has been obtained: two graphons $V, W$ are weakly isomorphic if and only if there exist measure-preserving maps $\varphi, \psi: I \to I$ such that $V\varphi = W\psi$ a.e. [1, Corollary 10.35]. Since $\varphi, \psi$ might not be invertible, this case cannot be easily understood with the above tools. However, the following interesting result holds true: when graphons $V, W$ are weakly isomorphic, $V$ is connected if and only if $W$ is connected. Indeed, by [15, Corollary 3.9], two graphons $V$ and $W$ correspond to the limit of a same graph sequence if and only if $\delta_{\square}(V, W) = 0$, where $\delta_{\square}$ is the cut distance, see e.g. [1, Sect. 8.2] for its definition. Moreover, $\delta_{\square}(V, W) = 0$ is equivalent to $V, W$ being weakly isomorphic [1, Corollary 10.34]. Then, by [16, Theorem 1.16], a graphon is connected if and only if the corresponding graph limit is connected; since two weakly isomorphic graphons $V$ and $W$ correspond to the same graph limit, either they are both connected or both not connected.

### B. Spectrum of the graphon-Laplacian operator, connectedness, and degree.

In analogy with the adjacency and Laplacian matrices of a graph, the following operators have been defined, acting on $L^2(I)$, the space of square-integrable functions on the interval $I$.

$\mathcal{T}_W: L^2(I) \to L^2(I)$ is the following integral operator with kernel $W$, sometimes called adjacency operator:

$$ (\mathcal{T}_W f)(x) = \int_I W(x, y)f(y) \, dy. $$

The degree of the graphon $W$ is the function $d_W: I \to I$ defined by

$$ d_W(x) = \int_I W(x, y) \, dy, $$

and the graphon-Laplacian operator $\mathcal{L}_W: L^2(I) \to L^2(I)$ is

$$ \mathcal{L}_W = \mathcal{M}_{d_W} - \mathcal{T}_W, $$

where $\mathcal{M}_{d_W}: L^2(I) \to L^2(I)$ is the multiplication operator which multiplies by the degree $d_W$, i.e.,

$$ (\mathcal{M}_{d_W} f)(x) = d_W(x)f(x). $$

In other words,

$$ (\mathcal{L}_W f)(x) = \int_I W(x, y)(f(x) - f(y)) \, dy. $$

We summarize here some important properties of the spectrum of $\mathcal{L}_W$, see [6, Remark 1], [5, Remark 2] and references therein for more details.

**Proposition 1:** $\mathcal{L}_W$ is a self-adjoint operator. The spectrum $\sigma(\mathcal{L}_W)$ is real; its minimum is $\min \sigma(\mathcal{L}_W) = 0$ and its essential supremum satisfies $\ess \sup \sigma(\mathcal{L}_W) \le 2 \|d_W\|_{\infty}$. The spectrum $\sigma(\mathcal{L}_W)$ consists of the essential range of the degree function $d_W$ (which is the essential spectrum of $\mathcal{L}_W$) and at most countably many isolated eigenvalues with finite multiplicity. $\square$

The main relation between the spectrum of $\mathcal{L}_W$ and connectedness of $W$ is Proposition 2, which gives a result about the dimension of the kernel $\ker \mathcal{L}_W$ (in other words, of the eigenspace of the zero eigenvalue). We will use the notation $\mathbf{1}_A$ to denote the indicator function of a set $A \subseteq I$, i.e., $\mathbf{1}_A(x) = 1$ if $x \in A$ and $\mathbf{1}_A(x) = 0$ else. With this notation, $\operatorname{span}(\mathbf{1}_I) \subseteq L^2(I)$ is the set of essentially constant functions.

**Proposition 2:** $W$ is connected if and only if $\ker(\mathcal{L}_W) = \operatorname{span}(\mathbf{1}_I)$. $\square$

This result has been shown in [17, Theorem 4.1]. The implication 'W connected implies $\ker(\mathcal{L}_W) = \operatorname{span}(\mathbf{1}_I)$' has been also shown in [5, Prop. 7], based on tools from [18], and the converse is immediate from considering the two functions $\mathbf{1}_A, \mathbf{1}_{A^c}$ that are two orthogonal eigenfunctions of the zero eigenvalue when $W = 0$ a.e. $A \times A^c, \mu(A) \in (0, 1)$.

The analogous result of Proposition 2 for the normalized graphon-Laplacian has been obtained in [4, Proposition 6.2] and [18, Section 3.3].

Notice that $\ker(\mathcal{L}_W) = \operatorname{span}(\mathbf{1}_I)$ only ensures that the eigenspace of the zero eigenvalue has dimension one, but it does not ensure that zero is an isolated eigenvalue, since zero could be part of the essential spectrum, in case zero lies in the essential range of $d_W$. This leads us to the following result, where we will use the standard notation $\operatorname{ess \, inf} d_W$ to denote the essential infimum of the function $d_W$, and $\langle \cdot, \cdot \rangle$ and $\| \cdot \|_2$ to denote the scalar product and the norm in $L^2(I)$.

**Theorem 1:** For a graphon $W$, the following are equivalent:

(a) $W$ is connected and $\operatorname{ess \, inf} d_W > 0$;

(b) 0 is a simple isolated eigenvalue of $\mathcal{L}_W$;

(c) $a(W) > 0$, where $a(W)$ is the algebraic connectivity

$$ a(W) = \inf_{f \in (\operatorname{span} \mathbf{1}_I)^\perp, f \neq 0} \frac{\langle \mathcal{L}_W f, f \rangle}{\|f\|_2^2}. $$

*Proof:* The implication (a) $\Leftrightarrow$ (b) follows from Propositions 1 and 2 (see the proof of [5, Theorem 1] for more details). The implication (b) $\Leftrightarrow$ (c) is the min-max theorem for self-adjoint operators, together with the fact that $\min \sigma(\mathcal{L}_W) = 0$ and $\mathcal{L}_W \mathbf{1}_I = 0$. $\square$

Theorem 1 is the reason why two conditions that $W$ is connected and that the degree is essentially bounded away from zero, together, play a crucial role in convergence to consensus, see e.g. [2], [3], [9], [5].

For a graph, being connected clearly implies that each vertex has degree at least one. For a graphon $W$, instead, the assumption that $d_W$ is essentially bounded away from zero is an extra assumption, that does not follow from the assumption that $W$ is connected, as discussed below.

The assumption that $W$ is connected has the following implication on the positivity of the degree, that was noticed e.g. in [4], [18].

**Proposition 3:** If $W$ is connected, then $d_W > 0$ a.e.

*Proof:* If there exists $A \subseteq [0, 1]$ with $\mu(A) > 0$ such
that $d_W(x) = 0$ for all $x \in A$, then

$$ \int_{A \times A^c} W(x, y) \, dx \, dy \le \int_{A \times I} W(x, y) \, dx \, dy \\ = \int_A \left( \int_I W(x, y) \, dy \right) \, dx = \int_A d_W(x) \, dx = 0, $$

where the first equality follows from Fubini-Tonelli since the integrand is non-negative.

If $\mu(A) \in (0, 1)$, $\int_{A \times A^c} W(x, y) \, dx \, dy = 0$ means that $W$ is not connected. If $\mu(A) = 1$, $\int_{A \times I} W(x, y) \, dx \, dy = 0$ implies $W = 0$ a.e. $I^2$ and hence $W$ is not connected. $\square$

However, $W$ being connected does not imply that $\text{ess inf } d_W > 0$. For example, the graphon $W(x, y) = xy$ is connected, since $W(x, y) > 0$ except for $(x, y) = (0, 0)$, but it has degree $d_W(x) = \frac{1}{2}x$ and hence $\text{ess inf } d_W = 0$.

The other implication is not true either: $\text{ess inf } d_W > 0$ does not imply $W$ being connected. For example $W(x, y) = \mathbf{1}_{A \times A} + \mathbf{1}_{A^c \times A^c}$ for some $A$ such that $\mu(A) \in (0, 1)$ is not connected, but has $d_W(x) \ge \min\{\mu(A), \mu(A^c)\} > 0$ for all $x$.

We can obtain that one of the two conditions implies the other when we add suitable additional assumptions on $W$.

When $W$ is a regular graphon, i.e., it has essentially constant degree ($d_W(x) = \bar{d}$ a.e. for some $\bar{d} \ge 0$), then $W$ being connected implies that $d_W > 0$ a.e., and hence $\bar{d} > 0$, thus ensuring $\text{ess inf } d_W = \bar{d} > 0$.

When $W$ is continuous, instead, $\text{ess inf } d_W > 0$ implies that $W$ is connected, as shown in Proposition 4 below. Notice that when $W$ is continuous, also $d_W$ is continuous, and hence $\text{ess inf } d_W = \min d_W$.

**Proposition 4:** If $W$ is a continuous graphon, the assumption $\text{ess inf } d_W > 0$ implies that $W$ is connected.

**Proof:** We will show that if $W$ is continuous and $W$ is not connected, then $d_W(\xi) = 0$ for some $\xi$ and hence $\min d_W(x) = 0$.

$W$ not connected means that $W(x, y) = 0$ a.e. in $A \times A^c$, for some $A$ with $\mu(A) \in (0, 1)$. Since $W$ is continuous, then $W(x, y) = 0$ for all $(x, y) \in (A \times A^c) = \bar{A} \times \bar{A}^c$, where $\bar{S}$ denotes the closure of a set $S$. Also notice<fnref n="1" /> that $\bar{A} \cap \bar{A}^c \ne \emptyset$. Consider $\xi \in \bar{A} \cap \bar{A}^c$ and notice that $W(\xi, y) = 0$ for all $y \in \bar{A}^c$ (since $(\xi, y) \in \bar{A} \times \bar{A}^c$) and $W(\xi, y) = 0$ for all $y \in \bar{A}$ (since $(\xi, y) \in \bar{A}^c \times \bar{A}$). Hence $W(\xi, y) = 0$ for all $y \in [0, 1]$. This further implies $d_W(\xi) = 0$. $\square$

**Remark 1:** In the case where $W$ is continuous, some papers (in particular [19]) consider the graphon Laplacian as an operator $\mathcal{L}_W : \mathcal{C}(I) \to \mathcal{C}(I)$ (where $\mathcal{C}(I)$ is the space of continuous functions) instead of $\mathcal{L}_W : L^2(I) \to L^2(I)$ as in this paper, in order to obtain stronger convergence properties concerning graphs sampled from the graphon. Proposition 1 remains true in this setup, as well as the proof that if $W$ is connected then $\text{ker } \mathcal{L}_W = \text{span } \mathbf{1}_I$ (one of

the two implications in Prop. 2). However, the proof of the converse (when $W$ is not connected, dim $\ker \mathcal{L}_W > 1$) is obtained by considering the two orthogonal functions $\mathbf{1}_A$ and $\mathbf{1}_{A^c}$; such functions are not continuous, and hence are not eigenfunctions of $\mathcal{L}_W$ as an operator from $\mathcal{C}(I)$ to $\mathcal{C}(I)$. However, Theorem 1 remains true, since the condition that the degree is essentially bounded away from zero is still necessary for zero to be an isolated eigenvalue, and it implies $W$ being connected (thanks to $W$ being continuous, see Prop. 4).

In summary, if $W$ is continuous, then Prop. 1 and Theorem 1 hold true both in the case where $\mathcal{L}_W$ is considered as an operator $\mathcal{L}_W : \mathcal{C}(I) \to \mathcal{C}(I)$ and in the case where $\mathcal{L}_W$ is considered as an operator $\mathcal{L}_W : L^2(I) \to L^2(I)$, and condition (a) in Theorem 1 can be replaced by the equivalent condition $\min d_W > 0$. $\square$

### III. EQUIVALENT NOTIONS OF CONNECTEDNESS

In this section we present other notions of connectedness, which can be proved equivalent to Definition 1.

#### A. *Finitely connected graphons*

The paper [17] introduces a characterization of connected graphons, analogous to the characterization of irreducible matrices (a square non-negative matrix $A$ is irreducible if and only if for each $i, j$ there exists $m$ such that $[A^m]_{ij} > 0$).

In analogy with matrix powers, where $A^1 = A$ and for $m \ge 2$ $[A^m]_{ij} = \sum_{s_1, \dots, s_{m-1}} A_{is_1} \prod_{k=1}^{m-2} A_{s_k s_{k+1}} A_{s_{m-1}j}$, one can define $W^{\circ 1}(x, y) = W(x, y)$ and for $m \ge 2$

$$ W^{\circ m}(x, y) = \int_{I^{m-1}} W(x, s_1) \prod_{k=1}^{m-2} W(s_k, s_{k+1}) W(s_{m-1}, y) \, ds_1 \dots ds_{m-1}, $$

where in the case $m = 2$ by convention $\prod_{k=1}^0 \dots = 1$. Notice that for any $m \ge 1$

$$ \mathcal{T}_{W^{\circ m}} f = (\mathcal{T}_W)^m f, $$

where $(\mathcal{T}_W)^m = \mathcal{T}_W \circ \dots \circ \mathcal{T}_W$ (m times).

**Definition 2 (Finitely connected graphon [17]):** A graphon $W$ is finitely connected if for any $A, B \subseteq [0, 1]$ with $\mu(A) > 0$ and $\mu(B) > 0$ there exists a positive integer $m$ such that

$$ \int_{A \times B} W^{\circ m}(x, y) \, dx \, dy > 0. \quad \square $$

The equivalence of finitely connected and connected is proved in [17, Theorem 4.1]. Using tools from [17] and [16], we can also obtain a slightly different characterization, which we state as item (iii) in the following theorem.

**Theorem 2:** For a graphon $W$, the following are equivalent:

(i) $W$ is connected;

(ii) $W$ is finitely connected;

(iii) For a.e. $(x, y) \in I^2$, there exists a positive integer $m$ such that $W^{\circ m}(x, y) > 0$. $\square$

The proof is given in Appendix A.

<footnote n="1">¹$\bar{A} \cap \bar{A}^c = \partial A$ (the boundary of $A$). Notice that $\partial A = \emptyset$ implies that $A$, its interior and its closure are all equal, and hence $A$ is both open and closed, which can only happen when $A$ is empty and when $A$ is the whole space, here $[0, 1]$. Since here $A$ is neither empty nor the whole $[0, 1]$, its boundary is non-empty.</footnote>
## B. Path-connected graphons

A series of papers [2], [3], [9] have a different definition of connected, inspired from the classical definition of connected graphs (for each pair of distinct vertices $i, j$, there exist a path from $i$ to $j$). Such papers consider directed graphons, i.e., they do not assume $W$ is symmetric, and hence they define strongly connected graphons, in analogy with strongly connected graphs. Here we are interested in their definition, but restricted to the symmetric case, when it should be the analogous of connected graphs. Their definition has two items, one of which is ess inf $d_W > 0$, and the other which is meant to ensure that $\ker L = \operatorname{span} \mathbf{1}_I$ (and hence should be equivalent to connectedness as in Definition 1 in the symmetric case, per Prop. 2). We have seen in Theorem 1 that both assumptions ess inf $d_W > 0$ and $W$ connected, together, are equivalent to zero being a simple isolated eigenvalue of $L_W$, but we prefer to keep the assumption ess inf $d_W$ separate from the definition of connectedness, both for consistency with literature on graphons [1], [16] and so as to be able to discuss implications of each of the two assumptions.

This leads us to give the following definition of path-connected graphon, inspired by the definition of (strongly) connected graphon in [2], [3], [9] but different in the choice of not including the extra assumption concerning the degree, and in some technical details that will be discussed at the end of this subsection.

**Definition 3 (Edges and paths):** Consider $x, y \in I$. We say that $(x, y)$ is an edge if $(x, y)$ is a Lebesgue point of $W$ and $W(x, y) > 0$.

We say that there is a path of length $\ell$ from $x$ to $y$ if there exists $x_1, \dots, x_{\ell-1} \in I$ such that $(x_{k-1}, x_k)$ is an edge for all $k = 1, \dots, \ell$, with $x_0 = x$ and $x_\ell = y$.

**Definition 4 (Path-connected graphon):** A graphon $W$ is path-connected if for almost all $(x, y) \in I^2$ there exists a path from $x$ to $y$.

The definition of edges (and hence of paths and path-connectedness) involves Lebesgue points of $W$. We recall here the definition; for simplicity, we use square neighborhoods, but equivalently balls can be used, or any other family of sets with bounded eccentricity (not arbitrary rectangles): $(x, y)$ is a Lebesgue point of $W$ if

$$ \lim_{\rho \to 0} \frac{1}{(2\rho)^2} \int_{B_{\rho}(x) \times B_{\rho}(y)} |W(x, y) - W(s, z)| \, ds \, dz = 0, $$

where $B_{\rho}(x) = (x - \rho, x + \rho)$.

This implies (but is not equivalent to)

$$ W(x, y) = \lim_{\rho \to 0} \frac{1}{(2\rho)^2} \int_{B_{\rho}(x) \times B_{\rho}(y)} W(s, z) \, ds \, dz. $$

Denote by $L \subseteq I^2$ the set of Lebesgue points of $W$. Since $W$ is integrable, Lebesgue differentiation theorem ensures that $\mu(L) = 1$.

The following result, together with Prop. 2, ensures that path-connectedness as in Definition 4 is equivalent to $\ker L_W = \operatorname{span}(\mathbf{1}_I)$.

**Theorem 3:** A graphon $W$ is connected if and only if it is path-connected. □

The proof is given in Appendix B and C.

Theorem 3 holds true when edges are defined as in Definition 3, but it fails when the definition is modified by dropping the request that $(x, y)$ is a Lebesgue point of $W$, or replacing it with the request that $y$ is a Lebesgue point of $W(x, \cdot)$, as it will be demonstrated by an example in Subsection IV-B. Also, Theorem 3 fails when the definition of edges is modified by replacing the assumption $W(x, y) > 0$ with the assumption $(x, y) \in \operatorname{ess\,suppt} W$ or with the assumption $y \in \operatorname{ess\,suppt} W(x, \cdot)$, where $\operatorname{ess\,suppt}$ denotes the essential support; this is shown by the examples in Subsection IV-C.

# IV. EXAMPLES

## A. Example 1: Stochastic block model

A stochastic block model graphon is a piece-wise constant graphon $W$ with a finite number of pieces: $J_1 \cup \dots \cup J_r$ is a partition of $I$ into disjoint non-empty intervals such that $W$ is constant on each rectangle $J_i \times J_j$, say $W(x, y) = w_{ij}$ for all $(x, y) \in J_i \times J_j$. Its associated graph is a graph with $r$ vertices, and an edge $(i, j)$ if and only if $w_{ij} > 0$.

A stochastic block model graphon is connected if and only if its associated graph is connected.

An easy proof of this fact can be obtained using Definition 2 (thanks to Theorem 2), as follows.

For the stochastic block model graphon, for all $(x_0, \dots, x_m) \in J_{h_0} \times \dots \times J_{h_m}$,

$$ \prod_{k=0}^{m-1} W(x_k, x_{k+1}) = \prod_{k=0}^{m-1} w_{h_k, h_{k+1}}. $$

Hence, for all $x \in J_i$ and $y \in J_j$, setting $h_0 = i$ and $h_m = j$ we have

$$ W^{\circ m}(x, y) = \sum_{h_1=1}^{r} \dots \sum_{h_{m-1}=1}^{r} \mu(J_{h_1} \times \dots \times J_{h_{m-1}}) \prod_{k=0}^{m-1} w_{h_k, h_{k+1}}. $$

Now notice that $\prod_{k=0}^{m-1} w_{h_k, h_{k+1}} > 0$ if and only if $(h_0, \dots, h_m)$ is a path in the associated graph. Hence, for any $(x, y) \in J_i \times J_j$, $W^{\circ m}(x, y) > 0$ if and only if there exists a path of length $m$ from $i$ to $j$ in the associated graph.

## B. Example 2: Definition of edge $(x, y)$ needs $(x, y)$ Lebesgue point of $W$

The following example shows that the assumption $(x, y) \in L$ in the definition of edge plays a crucial role, and cannot be removed, nor be replaced by the assumption $y$ a Lebesgue point of $W(x, \cdot)$.

**Example 2:** Consider $A = [0, a]$ for some $a \in (0, 1)$, and define $\tilde{W} = \mathbf{1}_{A \times A} + \mathbf{1}_{A^c \times A^c}$. Then consider the graphon $\tilde{W}$ obtained by modifying $W$ on a zero-measure set as follows. For some $\alpha \in (0, 1)$, $0 < b_1 < c_1 < a$, and $1 > b_2 > c_2 > a$,

* change $W(b_1, y)$ into $\tilde{W}(b_1, y) = \alpha$ for all $y \in [c_1, 1]$,

* change $W(x, b_1)$ into $\tilde{W}(x, b_1) = \alpha$ for all $x \in [c_1, 1]$,

* change $W(b_2, y)$ into $\tilde{W}(b_2, y) = \alpha$ for all $y \in [0, c_2]$,
<figure><img src="image_3.png" /><figcaption>Fig. 1. Example 2: Graphon $\tilde{W}$. Blue is 1, white is 0, and red is $\alpha$.</figcaption></figure>

• change $W(x, b_2)$ into $\tilde{W}(x, b_2) = \alpha$ for all $x \in [0, c_2]$. The graphon $\tilde{W}$ is illustrated in Figure 1. By construction, $\tilde{W}$ is not connected, since it is zero a.e. $A \times A^c$.

Define $\tilde{L}_x = \{y : y$ is a Lebesgue point of $\tilde{W}(x, \cdot)\}$. We recall the definition: $y$ is a Lebesgue point of $\tilde{W}(x, \cdot)$ when

$$ \lim_{\rho \to 0} \frac{1}{2\rho} \int_{B_{\rho}(y)} |\tilde{W}(x, y) - \tilde{W}(x, z)| \, dz = 0, $$

where $B_{\rho}(y) = (y - \rho, y + \rho)$. This implies, but is not equivalent to, $\lim_{\rho \to 0} \frac{1}{2\rho} \int_{B_{\rho}(y)} \tilde{W}(x, z) \, dz = W(x, y)$.

With the above definition of Lebesgue point, we can easily compute

$$ \tilde{L}_x = \begin{cases} (0, 1) \setminus \{a, b_2\} & \text{if } x \in [0, b_1) \cup (b_1, c_1) \\ (0, 1) \setminus \{c_1\} & \text{if } x = b_1 \\ (0, 1) \setminus \{b_1, a, b_2\} & \text{if } x \in [c_1, c_2] \\ (0, 1) \setminus \{b_1, a\} & \text{if } x \in (c_2, b_2) \cup (b_2, 1] \\ (0, 1) \setminus \{c_2\} & \text{if } x = b_2. \end{cases} $$

Hence, when considering a modified definition of edges where $(x, y)$ is an edge when $\tilde{W}(x, y) > 0$ and $y$ is a Lebesgue point of $\tilde{W}(x, \cdot)$, one would obtain that $(x, y)$ is an edge for all

$$ y \in \begin{cases} (0, a) & \text{if } x \in [0, b_1) \cup (b_1, c_1) \\ (0, 1) \setminus \{c_1\} & \text{if } x = b_1 \\ (0, a) \setminus \{b_1\} & \text{if } x \in [c_1, a] \\ (a, 1) \setminus \{b_2\} & \text{if } x \in (a, c_2] \\ (a, 1) & \text{if } x \in (c_2, b_2) \cup (b_2, 1] \\ (0, 1) \setminus \{c_2\} & \text{if } x = b_2. \end{cases} $$

This would imply that $\tilde{W}$ is path-connected.

Notice that the conditions $\tilde{W}(x, y) > 0$ and $y$ a Lebesgue point of $\tilde{W}(x, \cdot)$ imply that $y \in \text{ess suppt}(\tilde{W}(x, \cdot))$. Indeed, $\lim_{r \to 0} \frac{1}{2r} \int_{B_r(y)} \tilde{W}(x, z) \, dz = \tilde{W}(x, y) > 0$ implies that $\int_{B_r(y)} \tilde{W}(x, z) \, dz > 0$ for all sufficiently small $r$ and hence $y$ does not belong to any open set where $\tilde{W}(x, \cdot) = 0$ a.e. Recalling that $\text{ess suppt}(\tilde{W}(x, \cdot)) = I \setminus \{\Omega \text{ open set such that } \tilde{W}(x, \cdot) = 0 \text{ a.e. in } \Omega\}$, this means that $y \in \text{ess suppt} W(x, \cdot)$. Hence, the above-considered modified edges are consistent with the definition of strongly connected in [3].

When dropping the request about Lebesgue points, i.e., when considering an edge $(x, y)$ whenever $W(x, y) > 0$,

one would obtain that $\tilde{W}$ has a path from $x$ to $y$ for all $(x, y) \in I^2$ (as required in the definition of connectedness in [9]), and not just for almost all as above. Indeed, one would have edges $(x, b_1)$ for any $x \in [0, a]$, $(b_1, y)$ for any $y \in I$, $(x, b_2)$ for any $x \in (a, 1]$, and $(b_2, y)$ for any $y \in I$.

The degree is $d_{\tilde{W}}(x) = 1/2$ for all $x$, except for $b_1$ and $b_2$ where $d_{\tilde{W}}(b_1) = c_1 + \alpha(1 - c_1) = c_1(1 - \alpha) + \alpha > 0$ and $d_{\tilde{W}}(b_2) = \alpha c_2 + (1 - c_2) > 0$, so that $\text{ess inf } d_{\tilde{W}} = 1/2 > 0$, and $\text{inf } d_{\tilde{W}} = \min\{\frac{1}{2}, c_1(1 - \alpha) + \alpha, \alpha c_2 + (1 - c_2)\} > 0$, thus satisfying also the additional item in the definition of (strongly) connected in [3] and in [9].

This example also shows that, with the definition of edges as in [3], [9], the property of being path-connected would not be preserved when changing the graphon on a zero-measure set. Indeed, the graphon $W$ used in the construction of $\tilde{W}$ is not path-connected, also when using such modified definitions.

### C. Examples 3 and 4: Definition of edge $(x, y)$ needs $W(x, y) > 0$

We will present two examples, showing that the condition $W(x, y) > 0$ in the definition of edge cannot be replaced by the condition $(x, y) \in \text{ess suppt}(W)$, nor by the condition $y \in \text{ess suppt}(W(x, \cdot))$.

Both examples use the Smith-Volterra-Cantor set, of which we recall here the definition and a few relevant properties. The Smith-Volterra-Cantor $C$ is obtained with an iterative construction, where $C_0 = I$ and $C_{k+1}$ is obtained by removing from all the $2^k$ closed intervals that form $C_k$ their middle open intervals of length $\frac{1}{4^{k+1}}$. Then $C = \lim_{k \to \infty} C_k$ has measure $1/2$, is closed, and it does not contain any interval.

Consider $f: I \to I$ the indicator function of $C^c$, i.e., $f = 1_{C^c}$. Clearly its support is $\text{suppt}(f) = C^c$. The essential support, instead, is $\text{ess suppt}(f) = I$. Indeed, for any open $\Omega \subseteq I$, we have$^2 \mu(\Omega \cap C^c) > 0$. This means that there exists no open $\Omega$ on which $f$ is zero a.e., and hence $\text{ess suppt } f = I \setminus \{\Omega \text{ open set such that } f = 0 \text{ a.e. in } \Omega\} = I$.

Now consider the graphon $W(x, y) = f(x)f(y) = 1_{C^c \times C^c}$. We can show that the essential support of $W$ is $I^2$. Indeed, for any non-empty open $\Omega \subseteq I^2$, we have$^3 \mu(\Omega \cap (C^c \times C^c)) > 0$. This means that there exists no open $\Omega$ on which $W$ is zero a.e., and hence $\text{ess suppt } W = I^2 \setminus \{\Omega \text{ open set such that } W = 0 \text{ a.e. in } \Omega\} = I^2$.

<footnote>$^2$More in details: $\Omega \subseteq I$ open and non-empty implies that $\Omega$ contains a non-empty open interval $J$. Then $J$ is not a subset of $C$, since $C$ does not contain any interval. Hence $J \cap C^c \neq \emptyset$. Recall that $C^c$ is a union of open intervals, say $C^c = \bigcup_h B_h$ where $B_h$'s are open intervals. $J \cap \bigcup_h B_h \neq \emptyset$ implies that $J \cap B_h \neq \emptyset$ for some $h$. Then, recalling that both $J$ and $B_h$ are open intervals, this also implies that $\mu(J \cap B_h) > 0$ (actually $J \cap B_h$ is a non-empty open interval). Finally $\mu(\Omega \cap C^c) \geq \mu(J \cap B_h) > 0$.</footnote>

<footnote>$^3$More in details: $\Omega \subseteq I^2$ open and non-empty implies that $\Omega$ contains a non-empty set $J \times K$, with $J, K$ open intervals. Since $C$ does not contain any interval, $J \cap C^c \neq \emptyset$ and $K \cap C^c \neq \emptyset$. Recalling that $C^c = \bigcup_h B_h$ where $B_h$'s are open intervals, this implies that $J \cap B_j \neq \emptyset$ for some $j$ and $K \cap B_k \neq \emptyset$ for some $k$. Then, recalling that both $J$ and $B_h$ are open intervals, this also implies that $\mu(J \cap B_j) > 0$ and $\mu(K \cap B_k) > 0$ (actually $J \cap B_j$ and $K \cap B_k$ are non-empty open intervals). Finally $\mu(\Omega \cap (C^c \times C^c)) \geq \mu((J \cap B_j) \times (K \cap B_k)) > 0$.</footnote>
We have all the ingredients to give the following examples.

**Example 3:** Consider $W = \mathbf{1}_{C^c \times C^c} + \mathbf{1}_{C \times C}$. We have ess suppt($W$) $\supseteq$ ess suppt($\mathbf{1}_{C^c \times C^c}$) = $I^2$, which gives ess suppt($W$) = $I^2$. Clearly $W$ is not connected, since $W = 0$ on $C^c \times C$. However, when considering a modified definition of paths where $(x, y)$ is an edge when $(x, y) \in L$ and $(x, y) \in$ ess suppt($W$), one would obtain that $W$ is path-connected. Indeed, almost every $(x, y)$ is in $L$, and every $(x, y)$ is in ess suppt($W$) = $I^2$.

This shows the importance of using the stronger assumption $W(x, y) > 0$, which has been taken in Definition 3.

Notice that $W$ has constant degree $d_W(x) = \frac{1}{2}$ for all $x$, and hence ess inf $d_W = \frac{1}{2} > 0$.

**Example 4:** Define the following sets: $R_1 = C^c \cap [0, \frac{1}{2}]$, $R_2 = C^c \cap [\frac{1}{2}, 1]$, $C_1 = C \cap [0, \frac{1}{2}]$, and $C_2 = C \cap [\frac{1}{2}, 1]$. Notice that $C_1 \cup C_2 = C$ and $R_1 \cup R_2 = C^c$. Notice that, by reflection symmetry of $C$ and $C^c$ with respect to the point $\frac{1}{2}$, $\mu(R_1) = \mu(R_2) = \frac{1}{2}\mu(C^c) = \frac{1}{4}$ and $\mu(C_1) = \mu(C_2) = \frac{1}{2}\mu(C) = \frac{1}{4}$. Also notice that $C_1$ and $C_2$ are closed and they do not contain any interval.

Consider the graphon $W$ defined by

$$W = \mathbf{1}_{(C_1 \cup R_2) \times (C_1 \cup R_2)} + \mathbf{1}_{(C_2 \cup R_1) \times (C_2 \cup R_1)}$$

$W$ is not connected, since considering $A = C_1 \cup R_2$ we have $\mu(A) = \mu(A^c) = \frac{1}{2}$ and $W = 0$ a.e. $A \times A^c$. However, when considering a modified definition of paths where $(x, y)$ is an edge when $(x, y) \in L$ and $y \in$ ess suppt $W(x, \cdot)$, one would obtain that $W$ is path-connected, as we will show below. It is immediate to see that $W(x, \cdot) = \mathbf{1}_{C_1 \cup R_2}$ if $x \in C_1 \cup R_2$ and $W(x, \cdot) = \mathbf{1}_{C_2 \cup R_1}$ if $x \in C_2 \cup R_1$. We will show that the essential support of $W(x, \cdot)$ satisfies the following:

$$\text{ess suppt } W(x, \cdot) \supseteq [\frac{1}{2}, 1] = C_2 \cup R_2 \quad \text{if } x \in C_1 \cup R_2,$$

$$\text{ess suppt } W(x, \cdot) \supseteq [0, \frac{1}{2}] = C_1 \cup R_1 \quad \text{if } x \in C_2 \cup R_1.$$

To prove it for the case when $x \in C_1 \cup R_2$, we study $W(x, \cdot) = \mathbf{1}_{C_1 \cup R_2}$ and notice that ess suppt($\mathbf{1}_{C_1 \cup R_2}$) $\supseteq$ ess suppt($g$), where $g = \mathbf{1}_{R_2}$. Recall that ess suppt($g$) = $I \setminus \bigcup\{\Omega \text{ open set such that } g = 0 \text{ a.e. in } \Omega\}$. If an open set $\Omega$ has $\mu(\Omega \cap (\frac{1}{2}, 1]) > 0$, then $\mu(\Omega \cap R_2) > 0$, since $C_2$ does not contain any interval. This implies that $g$ is not a.e. zero on $\Omega$. If instead $\Omega$ has $\mu(\Omega \cap (\frac{1}{2}, 1]) = 0$, then $\Omega \cap (\frac{1}{2}, 1] = \emptyset$ (since non-empty open sets cannot have zero measure), i.e., $\Omega \subseteq [0, \frac{1}{2}]$. An open set $\Omega \subseteq [0, \frac{1}{2}]$ is such that $g = 0$ a.e. $\Omega$. Hence, $\bigcup\{\Omega \text{ open set such that } g = 0 \text{ a.e. in } \Omega\} = [0, \frac{1}{2})$, which gives ess suppt $g = I \setminus [0, \frac{1}{2}) = [\frac{1}{2}, 1] = C_2 \cup R_2$.

A similar proof can be done for the case $x \in C_2 \cup R_1$.

This result on the essential support of $W(x, \cdot)$ ensures that almost all elements of the following sets would be edges (if we consider the definition of edges as $(x, y) \in L$ such that $y \in W(x, \cdot)$): $C_1 \times C_2$, $C_1 \times R_2$, $R_2 \times C_2$, $R_2 \times R_2$, $C_2 \times C_1$, $C_2 \times R_1$, $R_1 \times C_1$, $R_1 \times R_1$. The presence of such edges is enough to construct a path between almost any pair of points.

The degree of $W$ is $d_W(x) = \frac{1}{2}$ for all $x$, except for $x = \frac{1}{2}$ where $d_W(\frac{1}{2}) = 1$, and hence ess inf $d_W = \frac{1}{2} > 0$.

Notice that $W$ is strongly connected according to the definitions in [2], [3].

## V. CONCLUSION

We presented some characterizations of graphon connectedness, that can be useful in works on large-scale diffusion-based dynamics, such as consensus, opinion dynamics, distributed optimization and synchronization. Future work can include extending these results to non-symmetric graphons, and studying connectedness of random graphs sampled from graphons (building upon some interesting recent results).

## VI. ACKNOWLEDGEMENT

The author acknowledges useful discussions with Paolo Frasca, Raoul Prisant, and Cédric Simal.

## REFERENCES

[1] L. Lovász, *Large Networks and Graph Limits*. American Mathematical Society, 2012.

[2] L. Boudin, F. Salvarani, and E. Trélat, “Exponential convergence towards consensus for non-symmetric linear first-order systems in finite and infinite dimensions,” *SIAM J. Math. Anal.*, vol. 54, no. 3, pp. 2727–2752, 2022.

[3] B. Bonnet, N. Pouradier-Duteil, and M. Sigalotti, “Consensus formation in first-order graphon models with time-varying topologies,” *Mathematical Models and Methods in Applied Sciences*, vol. 32, no. 11, pp. 2121–2188, 2022.

[4] J. Petit, R. Lambiotte, and T. Carletti, “Random walks on dense graphs and graphons,” *SIAM Journal on Applied Mathematics*, vol. 81, no. 6, pp. 2323–2345, 2021.

[5] R. Prisant, F. Garin, and P. Frasca, “The asymptotic behavior of the Altafini model on signed graphons,” in *European Control Conference, Thessaloniki, Greece, Jun. 2025*.

[6] ——, “Opinion dynamics on signed graphs and graphons,” *IEEE Trans. Control Network Systems*, 2025, in press.

[7] S. V. Nagpal, G. G. Nair, S. H. Strogatz, and F. Parise, “Synchro- nization in random networks of identical phase oscillators: A graphon approach,” *arXiv preprint arXiv:2403.13998*, 2024.

[8] J. J. Bramburger, M. Holzer, and J. Williams, “Persistence of steady states for dynamical systems on large networks,” *Journal of Nonlinear Science*, vol. 35, no. 6, Sep. 2025.

[9] Y. Chen and T. Li, “A large-scale stochastic gradient descent algorithm over a graphon,” in *62nd Annual Conference on Decision and Control (CDC)*, 2023, pp. 4806–4811.

[10] P. E. Caines and M. Huang, “Graphon mean field games and their equations,” *SIAM Journal on Control and Optimization*, vol. 59, no. 6, pp. 4373–4399, 2021.

[11] F. Parise and A. Ozdaglar, “Graphon games: A statistical framework for network games and interventions,” *Econometrica*, vol. 91, no. 1, pp. 191–225, 2023.

[12] M.-A. Belabbas and X. Chen, “Geometric characterization of the H-property for step-graphons,” *IEEE Transactions on Automatic Control*, vol. 69, no. 6, pp. 3849–3864, 2024.

[13] S. Gao and P. E. Caines, “Graphon control of large-scale networks of linear systems,” *IEEE Transactions on Automatic Control*, vol. 65, no. 10, pp. 4090–4105, 2019.

[14] M. T. Köhler, A. Makarow, and C. Kirches, “Integer control approximations for graphon dynamical systems,” *IEEE Control Systems Letters*, vol. 9, pp. 877–882, 2025.

[15] C. Borgs, J. Chayes, L. Lovász, V. Sós, and K. Vesztergombi, “Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing,” *Advances in Mathematics*, vol. 219, no. 6, pp. 1801–1851, 2008.

[16] S. Janson, “Connectedness in graph limits,” 2008. [Online]. Available: https://arxiv.org/abs/0802.3795

[17] C. Simal, J. Petit, and T. Carletti, “The shortest-path distance on graphons,” 2025. [Online]. Available: https://arxiv.org/abs/2506.14353

[18] A. Khetan and M. Mj, “Cheeger inequalities for graph limits,” *Annales de l'Institut Fourier*, vol. 74, no. 1, pp. 257–305, 2024.

[19] U. von Luxburg, M. Belkin, and O. Bousquet, “Consistency of spectral clustering,” *The Annals of Statistics*, vol. 36, no. 2, pp. 555–586, 2008.
# APPENDIX

## A. Proof of Theorem 2

The equivalence of (i) and (ii) is shown in [17, Theorem 4.1]. We will now use similar tools to show the equivalence of (i) and (iii) (and show again the equivalence of (i) and (ii) along the way).

A first ingredient is the following lemma from [17], which is proved within the proof of [17, Lemma 4.1].

**Lemma 1:** If $\int_{A \times A^c} W(x, y) \, dx \, dy = 0$, then $\int_{A \times A^c} W^{\circ m}(x, y) \, dx \, dy = 0$ for all $m \ge 1$. $\square$

With this lemma, it is easy to show that when $W$ is not connected, both items (ii) and (iii) or Theorem 2 fail. Indeed, when $W$ is not connected, $\int_{A \times A^c} W(x, y) \, dx \, dy = 0$ for some $A$ such that $\mu(A) > 0$ and $\mu(A^c) > 0$. By Lemma 1, this implies that $\int_{A \times A^c} W^{\circ m}(x, y) \, dx \, dy = 0$ for all $m \ge 1$, so that $W$ is not finitely connected. Moreover, this implies that for each $m \ge 1$, $W^{\circ m}(x, y) = 0$ for all $(x, y) \in (A \times A^c) \setminus Z_m$, where $Z_m$ is some zero-measure set. Hence, for all $(x, y) \in (A \times A^c) \setminus Z$, $W^{\circ m}(x, y) = 0$ for all $m \ge 1$, where $Z = \bigcup_{m=1}^{\infty} Z_m$. Notice that $\mu(Z) = 0$ and hence $\mu((A \times A^c) \setminus Z) = \mu(A \times A^c) > 0$, contradicting (iii).

We will now focus on proving the converse result, that $W$ connected implies both items (ii) and (iii) being true. A key ingredient is a result from [16], concerning the following suitably-defined neighborhoods. For any $x \in I$, define

$$ \mathcal{N}_x = \text{suppt}(W(x, \cdot)) = \{\xi \in I : W(x, \xi) > 0\}. $$

By symmetry of $W$, clearly we also have

$$ \mathcal{N}_x = \text{suppt}(W(\cdot, x)) = \{\xi \in I : W(\xi, x) > 0\}. $$

For any measurable $A \subseteq I$, define

$$ \mathcal{N}(A) = \text{suppt}(\mathcal{T}_W \mathbf{1}_A) = \{x \in I : \int_A W(x, y) \, dy > 0\}. $$

Such neighborhoods satisfy the following lemma, where $\mathcal{N}^m(A)$ denotes the iterated application of the operator $\mathcal{N}$, $m$ times, e.g., $\mathcal{N}^2(A) = \mathcal{N}(\mathcal{N}(A))$, and in general $\mathcal{N}^m(A) = \mathcal{N}^{m-1}(\mathcal{N}(A))$.

**Lemma 2** ([16], Lemma 5.1, items (i) and (v)): If $W$ is connected, then:

* For a.e. $y \in I$, $\mu(\mathcal{N}_y) > 0$;

* If $A \subseteq I$ has $\mu(A) > 0$, then

$$ \mu\left(\bigcup_{m=1}^{\infty} \mathcal{N}^m(A)\right) = 1. \quad \square $$

Another key ingredient is the following characterization of $\mathcal{N}^m(A)$.

**Lemma 3:** For any measurable $A \subseteq I$,

$$ \mathcal{N}^m(A) = \text{suppt}(\mathcal{T}_W^m \mathbf{1}_A). $$

**Proof:** The proof is by induction. The base case $m=1$ is true by definition: $\mathcal{N}(A) = \text{suppt}(\mathcal{T}_W \mathbf{1}_A)$. Now we

consider the inductive assumption $\mathcal{N}^m(A) = \text{suppt}(\mathcal{T}_W^m \mathbf{1}_A)$ and we prove that the same holds also for $m+1$. We have

$$ \begin{aligned} (\mathcal{T}_W^{m+1} \mathbf{1}_A)(x) &= \int_A W^{\circ(m+1)}(x, y) \, dy \\ &= \int_{I^2} W(x, s) W^{\circ m}(s, y) \mathbf{1}_A(y) \, dy \, ds \\ &= \int_I W(x, s) (\mathcal{T}_W^m \mathbf{1}_A)(s) \, ds. \end{aligned} $$

By inductive assumption, $\mathcal{T}_W^m \mathbf{1}_A$ has support $\mathcal{N}^m(A)$, so that

$$ (\mathcal{T}_W^{m+1} \mathbf{1}_A)(x) = \int_{\mathcal{N}^m(A)} W(x, s) (\mathcal{T}_W^m \mathbf{1}_A)(s) \, ds. $$

Moreover, for all $x \in \mathcal{N}^m(A)$, $(\mathcal{T}_W^m \mathbf{1}_A)(s) > 0$, which implies that the integrand $W(x, s)(\mathcal{T}_W^m \mathbf{1}_A)(s)$ is positive if and only if $W(x, s) > 0$. Hence, $\int_{\mathcal{N}^m(A)} W(x, s)(\mathcal{T}_W^m \mathbf{1}_A)(s) \, ds > 0$ if and only if $\int_{\mathcal{N}^m(A)} W(x, s) \, ds > 0$, i.e., $\text{suppt}(\mathcal{T}_W^{m+1} \mathbf{1}_A) = \text{suppt}(\mathcal{T}_W \mathbf{1}_{\mathcal{N}^m(A)})$, which ends the proof, since $\mathcal{N}^{m+1}(A) = \mathcal{N}(\mathcal{N}^m(A)) = \text{suppt}(\mathcal{T}_W \mathbf{1}_{\mathcal{N}^m(A)})$. $\square$

With these ingredients, we can show that (i) implies (iii). When $W$ is connected, by Lemma 2 for a.e. $y \in I$ we have $\mu(\mathcal{N}_y) > 0$ and $\mu(\bigcup_{m=1}^{\infty} \mathcal{N}^m(\mathcal{N}_y)) = 1$.

By Lemma 3,

$$ \begin{aligned} \mathcal{N}^m(\mathcal{N}_y) &= \text{suppt}((\mathcal{T}_W)^m \mathbf{1}_{\mathcal{N}_y}) = \text{suppt}(\mathcal{T}_{W^{\circ m}} \mathbf{1}_{\mathcal{N}_y}) \\ &= \{x : \int_{\mathcal{N}_y} W^{\circ m}(x, \xi) \, d\xi > 0\}. \end{aligned} $$

Now notice that $\int_{\mathcal{N}_y} W^{\circ m}(x, \xi) \, d\xi > 0$ if and only if $\int_{\mathcal{N}_y} W^{\circ m}(x, \xi) W(\xi, y) \, d\xi > 0$, since $W(\xi, y) > 0$ for all $\xi \in \mathcal{N}_y$ and both $W$ and $W^{\circ m}$ are non-negative. This, together with the simple remark that $W^{\circ(m+1)}(x, y) = \int_I W^{\circ m}(x, \xi) W(\xi, y) \, d\xi \ge \int_{\mathcal{N}_y} W^{\circ m}(x, \xi) W(\xi, y) \, d\xi$, ensures that

$$ \text{suppt}(W^{\circ(m+1)}(\cdot, y)) \supseteq \text{suppt}(\mathcal{T}_{W^{\circ m}} \mathbf{1}_{\mathcal{N}_y}) $$

and hence

$$ \begin{aligned} &\bigcup_{m=1}^{\infty} \text{suppt}(W^{\circ m}(\cdot, y)) \\ &\supseteq \bigcup_{m=2}^{\infty} \text{suppt}(W^{\circ m}(\cdot, y)) = \bigcup_{m=1}^{\infty} \text{suppt}(W^{\circ(m+1)}(\cdot, y)) \\ &\supseteq \bigcup_{m=1}^{\infty} \text{suppt}(\mathcal{T}_{W^{\circ m}} \mathbf{1}_{\mathcal{N}_y}) = \bigcup_{m=1}^{\infty} \mathcal{N}^m(\mathcal{N}_y), \end{aligned} $$

where the latter has measure one for almost every $y \in I$.

Define the sets $C_y = \bigcup_{m=1}^{\infty} \text{suppt}(W^{\circ(m)}(\cdot, y))$ and $C = \bigcup_{y \in I} C_y = \{(x, y) \in I^2 : W^{\circ m}(x, y) > 0 \text{ for some } m\}$. We have obtained above that for a.e. $y \in I$, $\mu(C_y) = 1$.
This further implies<fnref n="4" /> that $\mu(C) = 1$, which is item (iii) of Theorem 2.

The implication (i) implies (ii) follows in a very similar manner. Given A, B with positive measure, we study $\int_{A \times B} W^{\circ m}(x, y) dx dy$. Since W is connected and $\mu(B) > 0$, by Lemma 2 we have $\mu(\bigcup_{m=1}^{\infty} \mathcal{N}^m(B)) = 1$. This implies that there exists a positive integer $m$ such that $\mu(A \cap \mathcal{N}^m(B)) > 0$. Hence

$$ \int_{A \times B} W^{\circ m}(x, y) dx dy \geq \int_{(A \cap \mathcal{N}^m(B)) \times B} W^{\circ m}(x, y) dx dy \\ = \int_{A \cap \mathcal{N}^m(B)} \left( \int_B W^{\circ m}(x, y) dy \right) dx $$

which is positive, since Lemma 3 ensures that $\mathcal{N}^m(B) = \text{suppt } \mathcal{T}_{W^{\circ m}} \mathbf{1}_B = \{x : \int_B W^{\circ m}(x, y) dy > 0\}$.

### B. Proof of Theorem 3 – Connected implies path-connected.

**Definition 5 (Path-reachable sets):** For each $x \in I$, define $S_n(x)$ the set of points $y \in I$ such that there exists a path of length $\le n$ from $x$ to $y$, and $S_0(x) = \{x\}$. Define

$$ S(x) = \bigcup_{n=0}^{\infty} S_n(x). $$

**Proposition 5:** W is path-connected if and only if $\mu(S(x)) = 1$ for almost all $x \in I$.

**Proof:** Define $C := \{(x, y) \in I^2 \text{ s.t. } y \in S(x)\}$, i.e., the pairs $(x, y)$ such that there is a path from $x$ to $y$. By definition, W is path-connected if and only if $\mu(C) = 1$. By Fubini-Tonelli theorem,

$$ \mu(C) = \int_C 1 \, dx \, dy = \int_I \left( \int_{S(x)} 1 \, dy \right) \, dx = \int_I \mu(S(x)) \, dx. $$

Hence, $\mu(C) = 1$ if and only if $\mu(S(x) = 1)$ a.e. □

**Remark 2:** Define $L_x = \{y \text{ s.t. } (x, y) \in L\}$. The same proof as for Prop. 5 shows that $\mu(L_x) = 1$ for almost every $x$, since we know that $\mu(L) = 1$ by Lebesgue differentiation theorem. □

**Proposition 6:** The path-reachable sets of a graphon W satisfy the following properties.

1) For all $x$, there is no edge $(z, y)$ with $z \in S(x)$ and $y \in S(x)^c$.

2) For all $x$ and for almost all $z \in S(x)$, $\int_{S(x)^c} W(z, y) dy = 0$.

3) For almost all $x$, $\int_{S(x)^c} W(x, y) dy = 0$.

4) $\int_{S(x) \times S(x)^c} W(z, y) dz dy = 0$.

**Proof:**

1) If an edge $(z, y)$ existed with $z \in S(x) \setminus \{x\}$ and $y \in S(x)^c$, we could construct a path from $x$ to $y$ by appending the edge $(z, y)$ to a path from $x$ to $z$, which exists since $z \in S(x)$. Similarly, if an edge $(x, y)$ existed with $y \in S(x)^c$, such edge would be

$$ \mu(C) = \int_C 1 \, dx \, dy = \int_I \left( \int_{C_y} 1 \, dx \right) \, dy = \int_I \mu(C_y) = 1. $$

a path of length one from $x$ to $y$. In both cases, we would have constructed a path from $x$ to $y \in S(x)^c$, which is a contradiction.

2) By 1), for each $z \in S(x)$,

$$ L_z \cap \text{suppt}(W(z, \cdot)) \cap S(x)^c = \emptyset. $$

For almost all $z$, by Remark 2 we have $\mu(L_z) = 1$, and hence $\mu(\text{suppt}(W(z, \cdot)) \cap S(x)^c) = 0$, which further implies $\int_{S(x)^c} W(z, y) dy = 0$.

3) This has a similar proof as 2), recalling that $x \in S(x)$ by construction.

4) This immediately follows by Fubini-Tonelli and 2). □

**Proposition 7:** If W is connected, then $\mu(S(x)) > 0$ for almost all $x \in I$.

**Proof:** Define

$$ B := \{x \text{ s.t. } \mu(S(x)) = 0\} = \{x \text{ s.t. } \mu(S(x)^c) = 1\}. $$

For almost all $x \in B$,

$$ 0 = \int_{S(x)^c} W(x, y) \, dy = \int_I W(x, y) \, dy, $$

where the first equality comes from Prop. 6 and the second from the fact that $\mu(S(x)^c) = 1$ since $x \in B$. Hence, $\int_{B \times I} W(x, y) dx dy = 0$. If W is connected, this implies<fnref n="5" /> that $\mu(B) = 0$. □

**Proposition 8:** If W is connected, then W is path-connected.

**Proof:** Assume W is connected. By Prop. 6, $\int_{S(x) \times S(x)^c} W(x, y) dy dx = 0$. Since W is connected, this implies that $\mu(S(x)) = 0$ or $\mu(S(x)) = 1$. By Prop. 7, for almost all $x \in I$ we have $\mu(S(x)) > 0$ and hence $\mu(S(x)) = 1$. By Prop. 5, W is path-connected. □

### C. Proof of Theorem 3 – Path-connected implies connected.

Recall the notation $L$ for the Lebesgue points of W and $B_r(x)$ for the interval $B_r(x) := (x-r, x+r)$. In this section, we will also use the following notation:

* $S$ denotes the support of W,

* $S_m$ denotes the support of $W^{\circ m}$,

* $\times_{j=0}^m B_r(s_j) = B_r(s_0) \times \dots \times B_r(s_m)$, and

* $W^{\circ m} : I^{m+1} \to I$ is the function defined by

$$ W^{\circ m}(x_0, \dots, x_m) = \prod_{k=0}^{m-1} W(x_k, x_{k+1}). $$

With this notation, we have

$$ W^{\circ m}(x, y) = \int_{I^{m-1}} W^{\circ m}(x, x_1, \dots, x_{m-1}, y) \, dx_1 \dots dx_{m-1}. \quad (1) $$

A first useful lemma is the following.

<footnote n="4">⁴By Fubini-Tonelli theorem,</footnote>

<footnote n="5">⁵This was noticed in [16], in the proof of Lemma 5.1. Its quick proof is the following. If $\mu(B) = 1$, then $0 = \int_{B \times I} W(x, y) dx dy = \int_{I \times I} W(x, y) dx dy$, i.e., $W = 0$ a.e., and hence W is not connected. If $0 < \mu(B) < 1$, then $\int_{B \times I} W(x, y) dx dy = 0$ implies $\int_{B \times B^c} W(x, y) dx dy = 0$, and hence W is not connected.</footnote>
**Lemma 4:** If $s_0, \dots, s_m \in I$ are such that $(s_{j-1}, s_j) \in L$ for all $j = 1, \dots, m$, then $(s_0, \dots, s_m)$ is a Lebesgue point of $W^{\bullet m}$.

**Proof:** The proof is by induction. The base case $m=1$ is trivial since $W^{\bullet 1} = W$. Now we assume that this is true for $m-1$ (inductive assumption) and we prove it true for $m$. We have $s_0, \dots, s_m \in I$ such that $(s_{j-1}, s_j) \in L$ for all $j = 1, \dots, m$. Notice that $W^{\bullet m}(x_0, \dots, x_m) = W^{\bullet (m-1)}(x_0, \dots, x_{m-1})W(x_{m-1}, x_m)$. By the inductive assumption, $(s_0, \dots, s_{m-1})$ is a Lebesgue point of $W^{\bullet (m-1)}$ and by assumption $(s_{m-1}, s_m)$ is a Lebesgue point of $W$. Hence, for any $\varepsilon > 0$ we can find $\rho > 0$ such that, for all $r \le \rho$,

$$ \frac{1}{(2r)^m} \int_{\times_{j=0}^{m-1} B_r(s_j)} |W^{\bullet (m-1)}(x_0, \dots, x_{m-1}) - W^{\bullet (m-1)}(s_0, \dots, s_{m-1})| dx_0 \dots dx_{m-1} \le \frac{\varepsilon}{2} \quad (2) $$

and

$$ \frac{1}{(2r)^2} \int_{B_r(s_{m-1}) \times B_r(s_m)} |W(x_{m-1}, x_m) - W(s_{m-1}, s_m)| dx_{m-1} dx_m \le \frac{\varepsilon}{2}. \quad (3) $$

Since $W$ takes values in $[0, 1]$, if we multiply the left-hand side of (2) by $W(s_{m-1}, s_m)$, we obtain a smaller or equal value. Similarly, since $W^{\bullet (m-1)}$ takes values in $[0, 1]$, if we multiply the integrand in the left-hand side of (3) by $W^{\bullet (m-1)}(x_0, x_2, \dots, x_{m-1})$ for any fixed $x_0, \dots, x_{m-2} \in I$, we obtain a smaller or equal value. This further implies

$$ \frac{1}{(2r)^{m+1}} \int_{\times_{j=0}^{m} B_r(s_j)} |W^{\bullet (m-1)}(x_0, \dots, x_{m-1}) - W^{\bullet (m-1)}(s_0, \dots, s_{m-1})| W(s_{m-1}, s_m) dx_0 \dots dx_m \le \frac{\varepsilon}{2} \quad (4) $$

and

$$ \frac{1}{(2r)^{m+1}} \int_{\times_{j=0}^{m} B_r(s_j)} |W(x_{m-1}, x_m) - W(s_{m-1}, s_m)| W^{\bullet (m-1)}(x_0, x_1, \dots, x_{m-1}) dx_0 \dots dx_m \le \frac{\varepsilon}{2}. \quad (5) $$

Now we study

$$ \frac{1}{(2r)^{m+1}} \int_{\times_{j=0}^{m} B_r(s_j)} |W^{\bullet m}(x_0, \dots, x_m) - W^{\bullet m}(s_0, \dots, s_m)| dx_0 \dots dx_m. $$

Recalling that

$$ W^{\bullet m}(x_0, \dots, x_m) = W^{\bullet (m-1)}(x_0, \dots, x_{m-1})W(x_{m-1}, x_m), $$
we obtain

$$ \begin{aligned} & |W^{\bullet m}(x_0, \dots, x_m) - W^{\bullet m}(s_0, \dots, s_m)| \\ &= |W^{\bullet (m-1)}(x_0, \dots, x_{m-1})W(x_{m-1}, x_m) \\ & \quad - W^{\bullet (m-1)}(x_0, \dots, x_{m-1})W(s_{m-1}, s_m) \\ & \quad + W^{\bullet (m-1)}(x_0, \dots, x_{m-1})W(s_{m-1}, s_m) \\ & \quad - W^{\bullet (m-1)}(s_0, \dots, s_{m-1})W(s_{m-1}, s_m)| \\ & \le |W(x_{m-1}, x_m) - W(s_{m-1}, s_m)|W^{\bullet (m-1)}(x_0, \dots, x_{m-1}) \\ & \quad + |W^{\bullet (m-1)}(x_0, \dots, x_{m-1}) - W^{\bullet (m-1)}(s_0, \dots, s_{m-1})|W(s_{m-1}, s_m). \end{aligned} $$

This, together with (4) and (5), ensures

$$ \frac{1}{(2r)^{m+1}} \int_{\times_{j=0}^{m} B_r(s_j)} |W^{\bullet m}(x_0, \dots, x_m) - W^{\bullet m}(s_0, \dots, s_m)| dx_0 \dots dx_m \le \varepsilon. $$

Since for any $\varepsilon > 0$ we can find $\rho > 0$ such that this holds for all $r \le \rho$, we have obtained that $(s_0, \dots, s_m)$ is a Lebesgue point of $W^{\bullet m}$. $\square$

The next tool for the proof is the following.

**Lemma 5:** If there exists a path of length $m$ from $\bar{x}$ to $\bar{y}$, then

$$ \lim_{r \to 0} \frac{1}{(2r)^2} \mu(S_m \cap (B_r(\bar{x}) \times B_r(\bar{y}))) > 0. $$

**Proof:** We denote by $s_0, s_1, \dots, s_m$ the given path of length $m$ from $\bar{x} = s_0$ to $\bar{y} = s_m$.

With these $s_i$'s, we define the short-hand notation

$$ V_r(x, y) = \int_{\times_{j=1}^{m-1} B_r(s_j)} W^{\bullet m}(x, x_1, \dots, x_{m-1}, y) dx_1 \dots dx_{m-1} $$

and we notice that $W^{\bullet m}(x, y) \ge V_r(x, y)$ for all $(x, y)$ (as it is easy to see from (1)). This implies

$$ \mu(S_m \cap (B_r(x) \times B_r(y))) = \int_{B_r(\bar{x}) \times B_r(\bar{y})} \mathbf{1}_{S_m}(x, y) dx dy \\ \ge \int_{B_r(\bar{x}) \times B_r(\bar{y})} \mathbf{1}_{\text{suppt } V_r}(x, y) dx dy, \quad (6) $$

By definition, $\mathbf{1}_{\text{suppt } V_r}(x, y) = 1$ if $V_r(x, y) > 0$, and $\mathbf{1}_{\text{suppt } V_r}(x, y) = 0$ if $V_r(x, y) = 0$. Now notice that $V_r(x, y) \le (2r)^{m-1}$ and hence $\frac{V_r(x, y)}{(2r)^{m-1}} \le 1$ if $V_r(x, y) > 0$, and $\frac{V_r(x, y)}{(2r)^{m-1}} = 0$ if $V_r(x, y) = 0$. Hence, for all $(x, y)$,

$$ \mathbf{1}_{\text{suppt } V_r}(x, y) \ge \frac{V_r(x, y)}{(2r)^{m-1}}. $$

This, together with (6), gives

$$ \mu(S_m \cap (B_r(\bar{x}) \times B_r(\bar{y}))) \ge \int_{B_r(\bar{x}) \times B_r(\bar{y})} \frac{V_r(x, y)}{(2r)^{m-1}} dx dy. $$

Recalling the definition of $V_r$, dividing by $(2r)^2$ and taking the limit for $r \to 0$, this gives

$$ \begin{aligned} & \lim_{r \to 0} \frac{1}{(2r)^2} \mu(S_m \cap (B_r(\bar{x}) \times B_r(\bar{y}))) \\ & \ge \lim_{r \to 0} \frac{1}{(2r)^{m+1}} \int_{\times_{j=0}^{m} B_r(s_j)} W^{\bullet m}(x_0, \dots, x_m) dx_0 \dots dx_m. \end{aligned} $$

Finally, $s_0, \dots, s_m$ being a path implies that $W^{\bullet m}(s_0, \dots, s_m) > 0$ and, by Lemma 4, that $(s_0, \dots, s_m)$ is a Lebesgue point of $W^{\bullet m}$. Hence we can conclude that

$$ \begin{aligned} & \lim_{r \to 0} \frac{1}{(2r)^{m+1}} \int_{\times_{j=0}^{m} B_r(s_j)} W^{\bullet m}(x_0, \dots, x_m) dx_0 \dots dx_m \\ & = W^{\bullet m}(s_0, \dots, s_m) > 0. \end{aligned} $$
□

We now have the tools to prove the following.

**Proposition 9:** If $W$ is path-connected, then it is connected.

**Proof:** We assume that $W$ is path-connected. We want to show that if $A \subseteq I$ is such that $W = 0$ a.e. $A \times A^c$, then $\mu(A \times A^c) = 0$.

Hence, throughout this proof, $A$ is such that $W = 0$ a.e. $A \times A^c$. By Lemma 1, this also implies that $W^{\circ m} = 0$ a.e. $A \times A^c$, for all $m$.

For any $(x, y) \in I^2$ and any $r > 0$,

$$ 
\begin{aligned}
& \mu((A \times A^c) \cap (B_r(x) \times B_r(y))) \\
&= \mu((A \times A^c) \cap (B_r(x) \times B_r(y)) \cap S_m) \\
&\quad + \mu((A \times A^c) \cap (B_r(x) \times B_r(y)) \cap S_m^c) \\
&\le \mu((A \times A^c) \cap S_m) + \mu((B_r(x) \times B_r(y)) \cap S_m^c).
\end{aligned}
$$

Recalling that $W^{\circ m} = 0$ a.e. $A \times A^c$, $\mu((A \times A^c) \cap S_m) = 0$. Dividing by $(2r)^2$ and taking the limit for $r \to 0$, we obtain

$$ 
\begin{aligned}
\lim_{r \to 0} \frac{1}{(2r)^2} \mu((A \times A^c) \cap (B_r(x) \times B_r(y))) \\
\le \lim_{r \to 0} \frac{1}{(2r)^2} \mu((B_r(x) \times B_r(y)) \cap S_m^c) < 1,
\end{aligned}
$$

where the last inequality follows from Lemma 5.

We have obtained that if there is a path from $x$ to $y$, then

$$ \lim_{r \to 0} \frac{1}{r^2} \mu((A \times A^c) \cap (B_r(x) \times B_r(y))) < 1. $$

If moreover $(x, y)$ is a Lebesgue point of $1_{A \times A^c}$, then

$$ 
\begin{aligned}
1_{A \times A^c}(x, y) &= \lim_{r \to 0} \frac{1}{(2r)^2} \int_{B_r(x) \times B_r(y)} 1_{A \times A^c}(s, t) \, ds \, dt \\
&= \lim_{r \to 0} \frac{1}{(2r)^2} \mu((A \times A^c) \cap (B_r(x) \times B_r(y))) < 1.
\end{aligned}
$$

Since $1_{A \times A^c}(x, y)$ can only take values 0 or 1, $1_{A \times A^c}(x, y) < 1$ implies $1_{A \times A^c}(x, y) = 0$, i.e., $(x, y) \notin A \times A^c$. We have obtained that if there is a path from $x$ to $y$ and $(x, y)$ is a Lebesgue point of $1_{A \times A^c}$, then $(x, y) \notin A \times A^c$.

By assumption, $W$ is path-connected: a.e. $(x, y)$ there exists a path from $x$ to $y$. Moreover, by Lebesgue differentiation theorem, a.e. $(x, y)$ is a Lebesgue point of $1_{A \times A^c}$. Hence, for almost all $(x, y)$, we have $(x, y) \notin A \times A^c$. In other words, $\mu(A \times A^c) = 0$.

Under the assumption that $W$ is path-connected, we have shown that $W = 0$ a.e. $A \times A^c$ implies $\mu(A \times A^c) = 0$, which further implies that $\mu(A)$ is 0 or 1. This shows that $W$ is connected. □