A Cayley tree with a positive integer parameter 
, also called a 
-Cayley tree, is a finite tree in
which each non-leaf graph vertex has vertex
degree 
.
The singleton graph 
is included by convention. For 
, the members are 
and the two-vertex tree 
. Finite 2-Cayley trees are path
graphs. The unique 
-Cayley
tree on 
vertices is the star graph 
.
The illustration above shows the first few 3-Cayley trees, also called boron trees or binary trees in this unrooted sense. They have vertex
degree either 1 or 3, apart from the singleton convention. The numbers on 
, 2, ... vertices,
counted up to graph isomorphism, are 1, 1, 0,
1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 4, 0, 6, 0, 11, ... (OEIS A052120).
The broader convention for trivalent trees allows
vertex degree 2. Binary
trees use a root vertex and ordered children.
|
|
The illustrations above show the first few 4-Cayley and 5-Cayley trees.
The infinite 
-regular
tree, or Bethe lattice, is a connected acyclic infinite graph in which every vertex has vertex
degree 
.
For an integer 
, independent site percolation and bond
percolation on this infinite graph have percolation
threshold (Christensen 2002, pp. 5 and 10-11)
 |
After arriving along one edge, there are 
forward branches.
