Degree Bounds for Star-Free Graphs

From a Forbidden Star to a Degree Bound

A restriction on which subgraphs a graph may contain can impose a direct limit on the degrees of its vertices. For stars, this connection is exact: a vertex of sufficiently large degree supplies the center and leaves of a star. The handshake lemma then turns the degree limit into an upper bound on the number of edges.

Throughout, graphs are finite and simple. For a positive integer $s$, the star $K_{1,s}$ has one center joined to $s$ leaves. Saying that a graph contains $K_{1,s}$ as a subgraph requires the center-to-leaf edges, but does not require the leaves to be nonadjacent: extra edges among the chosen vertices are allowed. A graph is $K_{1,s}$-free if it contains no such subgraph.

Theorem: Let $G$ be a graph of order $n$, and let $s\ge 1$ be an integer. The graph $G$ is $K_{1,s}$-free if and only if $\deg(v)\le s-1$ for every $v\in V(G)$. Consequently, $$ |E(G)|\le \left\lfloor\frac{(s-1)n}{2}\right\rfloor. $$ Because a simple graph on $n$ vertices also has maximum degree at most $n-1$, the stronger combined bound is $$ |E(G)|\le \left\lfloor\frac{n\min(s-1,n-1)}{2}\right\rfloor. $$

Proof. First suppose that $G$ has a vertex $v$ with at least $s$ neighbors. Choose $s$ distinct neighbors of $v$. The edges from $v$ to those neighbors form a $K_{1,s}$ subgraph; any edges among the chosen neighbors do not prevent this, since the subgraph need not be induced. Thus a $K_{1,s}$-free graph has $\deg(v)\le s-1$ at every vertex. Conversely, if every degree is at most $s-1$, no vertex can serve as the center of a $K_{1,s}$, so the graph is $K_{1,s}$-free.

For the edge bound, the handshake lemma states that the sum of the degrees is twice the number of edges: each edge contributes one to the degree of each of its two endpoints. Hence $2|E(G)|=\sum_{v\in V(G)}\deg(v)\le n(s-1)$. Since $|E(G)|$ is an integer, it is at most $\lfloor n(s-1)/2\rfloor$. The simple-graph restriction also gives $\deg(v)\le n-1$, so each degree is at most $\min(s-1,n-1)$; applying the same degree sum argument gives the combined bound. $\square$

The first bound is a useful consequence of the forbidden-star condition. The second also uses the finite number of available neighbors. When $s\le n$, the two bounds agree. When $s>n$, the forbidden star is impossible on $n$ vertices anyway, and the simple-graph degree limit can be substantially stronger.

When Can the Bound Be Sharp?

Write $d=s-1$. If $d\le n-1$ and every vertex has degree $d$, the graph is $d$-regular and has $nd/2$ edges. Such a graph attains the first bound whenever $nd$ is even. If $nd$ is odd, that number is not an integer; the bound becomes $(nd-1)/2$, and equality would require a slightly different degree pattern.

Equality test: Suppose $d=s-1\le n-1$. If $nd$ is even, equality in $|E(G)|\le\lfloor nd/2\rfloor$ holds exactly when every vertex has degree $d$. If $nd$ is odd, equality holds exactly when the degree sum is $nd-1$, which requires one vertex to have degree $d-1$ and all other vertices to have degree $d$.

To justify the test, define the deficit at a vertex $v$ to be $d-\deg(v)$, a nonnegative integer. When $nd$ is even, attaining $nd/2$ edges means the degree sum is $nd$, so the sum of all deficits is zero. Every deficit must therefore be zero. When $nd$ is odd, attaining $(nd-1)/2$ edges means the degree sum is $nd-1$, so the deficits sum to one. Exactly one deficit is then one, and the rest are zero. These are necessary and sufficient degree conditions for equality, provided the indicated degree sequence is realized by a graph.

Worked Example: A Regular Graph Attaining the Bound

Let $G$ have vertex set $V=\{1,2,3,4,5,6\}$ and edge set $E=\{12,23,34,45,56,61\}$. This is the cycle $C_6$. Test the $K_{1,3}$-free bound.

Each vertex has exactly two neighbors, so every degree is $2$. Since $s=3$, the forbidden-star condition requires degree at most $s-1=2$; therefore $G$ is $K_{1,3}$-free. The bound gives $$ |E(G)|\le \left\lfloor\frac{(3-1)6}{2}\right\rfloor =\left\lfloor\frac{12}{2}\right\rfloor=6. $$ The listed edge set has six edges, so it attains the bound.

Check: Summing the six degrees gives $2+2+2+2+2+2=12$, and dividing by two gives $12/2=6$ edges, agreeing with the edge list and the bound.

A Construction That Explains the Parity Condition

The condition $nd$ even is not merely an arithmetic convenience. For $0\le d\le n-1$, it is sufficient for a simple $d$-regular graph to exist. This gives a broad family of examples attaining the star-free bound whenever $d=s-1$.

Proposition: For $n\ge1$ and $0\le d\le n-1$, there exists a simple $d$-regular graph on $n$ vertices if and only if $nd$ is even.

Proof. If a $d$-regular graph exists, its degree sum is $nd$. By the handshake lemma this sum equals twice its number of edges, so $nd$ must be even.

For the converse, the case $d=0$ is given by the graph with no edges. Suppose $d>0$, and label the vertices by the residues $0,1,\ldots,n-1$ modulo $n$. If $d$ is even, join each vertex $i$ to $i\pm1,i\pm2,\ldots,i\pm d/2$, with residues taken modulo $n$. These are $d$ distinct other vertices: $d\le n-1$ ensures the offsets do not include a full turn around the residues. The rule is symmetric, so it defines undirected edges, and every vertex has degree $d$.

If $d$ is odd, the assumption that $nd$ is even forces $n$ to be even. Join each vertex $i$ to $i\pm1,\ldots,i\pm(d-1)/2$, and also to the vertex $i+n/2$ modulo $n$. The paired offsets give $d-1$ distinct neighbors; the antipodal vertex is a further distinct neighbor because $(d-1)/2<n/2$. The rule is symmetric, including the antipodal edge, and every vertex has degree $d$. In both cases the construction gives a simple $d$-regular graph, proving sufficiency. $\square$

Worked Example: Equality When the Degree Product Is Odd

Let $G$ have $V=\{1,2,3,4,5\}$ and $E=\{12,13,14,23,24,35,45\}$. Test whether it attains the edge bound for $K_{1,4}$-free graphs.

Here $s=4$, so $d=s-1=3$. The degrees, computed from the edge list, are $\deg(1)=3$, $\deg(2)=3$, $\deg(3)=3$, $\deg(4)=3$, and $\deg(5)=2$. Thus all degrees are at most $3$, and $G$ is $K_{1,4}$-free. Since $nd=5\cdot3=15$, the bound is $$ |E(G)|\le \left\lfloor\frac{15}{2}\right\rfloor =\left\lfloor7.5\right\rfloor=7. $$ The displayed edge set contains seven edges, so equality holds. The degree pattern also matches the odd-product equality test: four vertices have degree $3$, and one has degree $2$.

Check: The degree sum is $3+3+3+3+2=14$, so the handshake lemma gives $14/2=7$ edges, exactly the number listed.

The Vertex Limit Can Strengthen the Bound

If $s>n$, the estimate based only on $s-1$ may be far from the best one, because no vertex can have more than $n-1$ neighbors. The combined bound accounts for this. In the extreme case $s>n$, every graph on $n$ vertices is $K_{1,s}$-free, and the combined bound is the usual complete-graph edge limit $n(n-1)/2$.

Worked Example: A Forbidden Star Too Large to Fit

Let $G$ be the complete graph on $V=\{1,2,3,4\}$, with $E=\{12,13,14,23,24,34\}$. Consider $K_{1,6}$-freeness. The ordinary degree bound gives $\deg(v)\le5$, and hence $$ |E(G)|\le \left\lfloor\frac{5\cdot4}{2}\right\rfloor =\left\lfloor10\right\rfloor=10. $$ This bound is weak: there are only three other vertices available to be neighbors of any one vertex. The combined degree bound is $\deg(v)\le\min(5,3)=3$, giving $$ |E(G)|\le \left\lfloor\frac{3\cdot4}{2}\right\rfloor =\left\lfloor6\right\rfloor=6. $$ The graph is $K_4$, so each vertex has degree $3$, and the six listed edges attain this sharper bound. It is $K_{1,6}$-free because no vertex has six neighbors.

Check: The four degrees sum to $3+3+3+3=12$, and $12/2=6$ edges, confirming the count directly.

Common Pitfall: Confusing Subgraphs with Induced Subgraphs

A common error is to treat a forbidden star as though it had to be an induced subgraph. For an ordinary subgraph, the selected center must be adjacent to each selected leaf, but edges among the leaves are allowed. For example, the triangle on $V=\{1,2,3\}$, $E=\{12,23,13\}$, contains $K_{1,2}$: choose vertex $1$ as the center and vertices $2$ and $3$ as leaves. The extra edge $23$ does not remove the two required edges $12$ and $13$.

The incorrect reasoning would be: “The triangle has no induced $K_{1,2}$, because the two neighbors of each vertex are adjacent; therefore it is $K_{1,2}$-free.” The correction is that the forbidden object here is a subgraph, not an induced subgraph. Indeed, each triangle vertex has degree $2$, and the degree criterion confirms that the triangle is not $K_{1,2}$-free.

In practice, the bound is most useful as a quick necessary condition: any proposed $K_{1,s}$-free graph with more than $\lfloor (s-1)n/2\rfloor$ edges is impossible. To show that a bound is sharp, however, one must exhibit a graph meeting it and verify its degrees; the inequality alone does not guarantee that a suitable graph exists for every choice of parameters.

Check Your Understanding

For each question, state the relevant degree condition and show the arithmetic needed for any edge count.

A graph has $n=8$ vertices and is $K_{1,3}$-free. What is the edge bound from the maximum-degree argument?
Can a $4$-regular graph on $7$ vertices exist? Justify your answer using the necessary parity condition.
For $n=5$ and $s=4$, what degree pattern is required if a $K_{1,4}$-free graph attains the edge bound?
Explain why $K_4$ contains $K_{1,2}$ as a subgraph even though it has no induced $K_{1,2}$.
If $s>n$, which degree restriction gives the sharper bound, and why?