Reference articles on history, science, culture and more
Surprise meSurprise meSubscribe
Encyclopedia

Star (graph theory)

Tree graph with one central node and leaves of length 1

Wikipedia contributorsAdapted for Fathomly · View authors
2 min read
Source updated November 18, 2025
Image credit is listed at the end of this article.

In graph theory, the star Sk is the complete bipartite graph K1, k, that is, it is a tree with one internal node and k leaves. Alternatively, some authors define Sk to be the tree of order k with maximum diameter 2, in which case a star of k > 2 has k − 1 leaves.

A star with 3 edges is called a claw.

The star Sk is edge-graceful when k is even and not when k is odd. It is an edge-transitive matchstick graph, and has diameter 2 (when k > 1), girth \infty (it has no cycles), chromatic index k, and chromatic number 2 (when k > 0). Additionally, the star has large automorphism group, namely, the symmetric group on k letters.

Stars may also be described as the only connected graphs in which at most one vertex has degree greater than one.

01Relation to other graph families

Claws are notable in the definition of claw-free graphs, graphs that do not have any claw as an induced subgraph. They are also one of the exceptional cases of the Whitney graph isomorphism theorem: in general, graphs with isomorphic line graphs are themselves isomorphic, with the exception of the claw and the triangle K3.

A star is a special kind of tree. As with any tree, stars may be encoded by a Prüfer sequence; the Prüfer sequence for a star K1,k consists of k − 1 copies of the center vertex.

Several graph invariants are defined in terms of stars. Star arboricity is the minimum number of forests that a graph can be partitioned into such that each tree in each forest is a star, and the star chromatic number of a graph is the minimum number of colors needed to color its vertices in such a way that every two color classes together form a subgraph in which all connected components are stars. The graphs of branchwidth 1 are exactly the graphs in which each connected component is a star.

The star graphs S3, S4, S5 and S6.
The star graphs S3, S4, S5 and S6.

02Other applications

The set of distances between the vertices of a claw provides an example of a finite metric space that cannot be embedded isometrically into a Euclidean space of any dimension.

The star network, a computer network modeled after the star graph, is important in distributed computing.

A geometric realization of the star graph, formed by identifying the edges with intervals of some fixed length, is used as a local model of curves in tropical geometry. A tropical curve is defined to be a metric space that is locally isomorphic to a star-shaped metric graph.

Watch videos about Star (graph theory)Explainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Star (graph theory)”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Images, from Wikimedia Commons:

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Continue exploring

Related topics

Starlike tree

In the mathematical subdiscipline of graph theory, a tree is said to be starlike if it has exactly one vertex of degree greater than 2. This high-degree vertex is the root, and a starlike tree can be seen as resulting from attaching to this central vertex at least three linear graphs (paths).

Homeomorphism (graph theory)

In graph theory, two graphs G {\displaystyle G} and G ′ {\displaystyle G'} are homeomorphic if there is a graph isomorphism from some subdivision of G {\displaystyle G} to some subdivision of G ′ {\displaystyle G'} . If the edges of a graph are thought of as lines drawn from one vertex to another, then two graphs are homeomorphic to each other in the graph-theoretic sense precisely if their diagrams are homeomorphic in the topological sense.

Link (simplicial complex)

The link in a simplicial complex is a generalization of the neighborhood of a vertex in a graph. The link of a vertex encodes information about the local structure of the complex at the vertex.