Unexpectedly, a Symmetry on Unlabeled Graphs

Abstract

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.