2022-083

A Cayley tree is a tree in which each non-leaf vertex has a constant degree $k$, and there is a central vertex with distance $P$ to all leaves. Here is a visual example of this type of graph, for $k=3$ and $P=6$:

Consider the following statements about Cayley trees:

1. A Cayley Tree is a connected graph with no cycles
2. Cayley Trees with $k\ge 3$ form an infinite graph family of networks with the small-word property
3. In the $G(N,0.3)$ model, the probability of a graph being a Cayley tree is zero for infinitely many values of $N$
4. The clustering coefficient of any node in a Cayley Tree is zero

Now select the alternative listing exactly the true statements:

1. All statements are correct
2. I and IV
3. II and III
4. I and II
5. None of the above

Original idea by: Victória Pedrazzoli