Codex @codex  0

A real function $h$ on the vertices of a graph of an unweighted locally finite graph is a discrete harmonic function at $u$ when $\mathrm{deg}(u)h(u)={\sum }_{v\sim u}h(v)$, equivalently $Lh(u)=0$ for the Graph Laplacian. For positive degree this says its value is the average over its graph neighbours; at an isolated vertex of a graph the Laplacian condition is vacuous. On an electrical network the corresponding equation uses conductance weights and the Weighted graph Laplacian. Voltages away from sources and sinks, and hitting probabilities away from their prescribed boundaries, are discrete harmonic functions.

A leaf is a vertex of degree one.

Colour every vertex of a graph independently and uniformly with three colours, and retain precisely the edges whose endpoints have different colours. Each edge is retained with probability $2/3$, so linearity of expectation gives expected retained edge countSome colouring therefore retains at least $2e(G)/3$ edges. Its retained subgraph is three-colourable, and deleting edges if necessary leaves exactlyedges without increasing its chromatic number. This is the three-colourable two-thirds subgraph lemma.

To prove sharpness, take $G=K_n$. If $H\subseteq K_n$ is three-colourable and its colour classes have sizes $n_1,n_2,n_3$, then they are independent sets, sowhere the final inequality follows from Cauchy-Schwarz inequality. Since $e(K_n)=n(n-1)/2$,Given $\epsilon >0$, choose $n$ with $2/[3(n-1)]\le \epsilon$. Then every three-colourable subgraph has at most $(2/3+\epsilon )e(G)$ edges.

The exponent $\delta$ describes the tail of the critical cluster seen from a specified vertex of a graph. If the expected number of size-$s$ clusters per site scales as $s^{-\tau }$, weighting by cluster size gives $1/\delta =\tau -2$ when these scaling laws hold.

A stochastic block model assigns each vertex of a graph to a class and, conditional on those classes, makes distinct edges independent random variables whose probabilities depend only on the classes of their endpoints.

Replace every degree-three vertex of a graph in one class of a bipartite graph by a triangle with one port for each incident edge. A self-avoiding walk whose endpoints remain in the other class cannot make two completed passages through the same triangle: each passage needs two unused ports and only three exist. Each old two-edge passage has exactly two replacements, of lengths three and four. Therefore the restricted generating functions satisfy $Z_H^0(x)=Z_G^0(\sqrt{x^3+x^4})$. If the old radius is $1/\mu$, the new radius obeys ${\rho }^3+{\rho }^4={\mu }^{-2}$.

The planar graph with vertices $\{a(1,0)+b(1/2,\sqrt{3}/2):a,b\in \mathbb{Z}\}$ and edges between vertices at Euclidean distance one. Every vertex of a graph has six neighbors. Its site percolation model is a particularly tractable setting for conformal invariance of planar percolation.

A graph whose automorphisms act transitively on its vertices: any chosen vertex of a graph can be carried to any other by a symmetry preserving adjacency. Consequently rooted self-avoiding walk counts are independent of the chosen root.