In graph theory, a star S_k is the complete bipartite graph K_1,k: a tree with one internal node and k leaves (but, no internal nodes and k + 1 leaves when k = 1). Alternatively, some authors define S_k to be the tree of order k with maximum diameter 2; in which case a star of k > 2 has k - 1 leaves.