Smallest Simple Graph with One Vertex Adjacent to All Others

Theorem

Let $G = \struct {V, E}$ be a simple graph of order $n$.

Let $G$ be the simple graph with the smallest size such that one vertex is adjacent to all other vertices of $G$.

Then $G$ is the star graph of order $n$ and is of size $n - 1$.

Proof

In order for the one vertex in question to be adjacent to all the others, it needs to be incident to $n - 1$ edges.

This is the smallest number of edges required.

Hence $G$ is a star graph.

From Size of Star Graph, the size of $G$ is thus $n - 1$.

$\blacksquare$

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $1$: Mathematical Models: $\S 1.3$: Graphs: Problem $21$