A graph is k-regular if:
It has k edges.
Every vertex has degree k.
It has k vertices.
It is a tree with k leaves.