Unexpectedly, a Symmetry on Unlabeled Graphs

We exhibit the joint symmetric distribution of the following two parameters on the set of unlabeled simple connected graphs with n vertices. The first parameter is the maximal number of leaves attached to a vertex. The second parameter is the size of the largest set of vertices sharing the same closed neighborhood minus $1$. Apparently, this is the first example of a natural non-trivial equidistribution of graph parameters on unlabeled simple connected graphs with a fixed set of vertices. Our proof is enumerative, using the theory of species. Exhibiting an explicit bijection interchanging the two parameters remains an open problem.