Mathwords logoMathwords

Star Graph — Definition, Formula & Examples

A star graph is a graph where one central vertex is connected by an edge to every other vertex, and no other edges exist. It looks like a hub with spokes radiating outward.

The star graph SnS_n is the complete bipartite graph K1,nK_{1,n}, consisting of a single central vertex of degree nn adjacent to nn vertices each of degree 11. Equivalently, SnS_n is a tree on n+1n+1 vertices with exactly nn leaves.

Key Formula

∣V(Sn)∣=n+1,∣E(Sn)∣=n|V(S_n)| = n + 1, \quad |E(S_n)| = n
Where:
  • nn = Number of leaf vertices (equivalently, the degree of the central vertex)
  • ∣V∣|V| = Total number of vertices in the star graph
  • ∣E∣|E| = Total number of edges in the star graph

How It Works

To construct SnS_n, place one vertex at the center and connect it to nn other vertices with one edge each. The central vertex (the hub) has degree nn, while every other vertex (a leaf) has degree 11. Star graphs are the simplest examples of trees and are always both connected and bipartite. They appear frequently when analyzing network topologies, as they model systems where all communication passes through a single node.

Worked Example

Problem: Draw the star graph S4S_4 and determine its number of vertices, edges, and the degree sequence.
Step 1: Place one central vertex cc and four leaf vertices v1,v2,v3,v4v_1, v_2, v_3, v_4.
∣V∣=4+1=5|V| = 4 + 1 = 5
Step 2: Connect cc to each leaf with one edge: {c,v1},{c,v2},{c,v3},{c,v4}\{c,v_1\}, \{c,v_2\}, \{c,v_3\}, \{c,v_4\}.
∣E∣=4|E| = 4
Step 3: The central vertex has degree 4 and each leaf has degree 1, giving the degree sequence.
(4, 1, 1, 1, 1)(4,\, 1,\, 1,\, 1,\, 1)
Answer: S4S_4 has 5 vertices, 4 edges, and degree sequence (4,1,1,1,1)(4, 1, 1, 1, 1).

Why It Matters

Star graphs model hub-and-spoke network architectures used in computer networking and transportation logistics. In discrete mathematics courses, they serve as key examples and counterexamples when studying properties like tree characterization, graph coloring (chromatic number 2), and bounds on graph invariants like diameter (always 2 for n≥2n \geq 2).

Common Mistakes

Mistake: Confusing SnS_n vertex count: assuming SnS_n has nn total vertices instead of n+1n+1.
Correction: The subscript nn in SnS_n denotes the number of leaves (or equivalently, edges). The total vertex count is n+1n+1 because you must include the central hub vertex.