content_image/329988.jpg
all the correlation functions such that all of its members are greater than a small constant ϵ ′ > 0. 

In the following, we first present the concepts of open and closed borders in a graph for later use; we then define the ferromagnetic Ising model on a general graph and derive the equivalence of the sum over configurations and the sum over different borders. Next we prove a theorem stating a sufficient condition for a graph to exhibit spontaneous magnetization. Because of the technical nature of the theorem, we thoroughly examine its more and less immediate consequences for a wide range of different graphs. Lastly, we discuss our results and the current comprehension of the mechanism of spontaneous magnetization on graphs for the Ising model. 

## OPEN AND CLOSED BORDERS IN A GRAPH 

A graph G is a pair ( P , L ), where P is a countable collection of vertices and L ⊂ P × P is a set of unoriented bonds between points. Any pair G ′ = ( P $^{′}$, L $^{′}$), such that P ′ ⊂ P , L ′ contains only links between elements of P ′ and L ′ ⊂ L , is called a subgraph , and it’s denoted G ′ ⊂ G . We will restrict our attention to those graphs whose coordination number z$_{i}$ , representing the number of bonds in L having one extremum in i , is uniformly limited: an integer z$_{Max}$ > 0 exists such that z$_{i}$ ≤ z$_{Max}$ for all i ∈ P . 

We now define a path γ , between two points i and j , as a collection of consecutive bonds of L , where consecutive means that each pair shares a vertex with the next one: 

<img src='content_image/329988.jpg'>

Directly associated to the concept of path, the chemical distance between two points i and j is defined as the length of the shortest path connecting them. The chemical distance straightforwardly induces the so-called intrinsic metric of the graph. 

The intrinsic fractal dimension d$_{frac}$ of a graph, defined as the minimum d such that N$_{r}$ , the maximum number of vertices included in a Van Hove sphere[21] of radius r (i.e. the set of points within a chemical distance from a given point of no more than r bonds), satisfies N$_{r}$ ≤ r d as r → ∞ . It differs from the usual fractal dimension in that it refers to the topological nature of the graph (i.e. on its natural - chemical - distance), and not on the metric structure of the space into which the graph is embedded. 

