A Workshop on Small Forbidden-Graph Problems

Three Forbidden Graphs, Three Kinds of Bound

An extremal problem asks how many edges a graph can have while avoiding a specified subgraph. A construction with many edges gives a lower bound for this maximum; an argument applying to every admissible graph gives an upper bound. To determine the exact maximum, both bounds must agree. This workshop carries out that plan for the path \(P_3\), the triangle \(K_3\), and the three-leaf star \(K_{1,3}\).

Thus a graph is \(F\)-free if it has no copy of \(F\) as a subgraph. Each graph used below is specified by its vertices and edges, or by a precise rule for its edge set. We will treat \(n\ge 1\). The constructions establish that the bounds are attainable, not merely that they cannot be exceeded.

Forbidding a Three-Vertex Path

The graph \(P_3\) consists of three vertices and two edges joining them in a path. In a simple graph, a vertex of degree at least two has two distinct neighbors; those two incident edges form a \(P_3\), even if the neighbors are also adjacent. Conversely, every copy of \(P_3\) has a vertex of degree at least two in the ambient graph. So being \(P_3\)-free is equivalent to having maximum degree at most one.

Proof. Let \(G\) be any \(P_3\)-free graph on \(n\) vertices. Every vertex has degree at most one. Each edge therefore uses two vertices that are incident with no other edge. The edges have pairwise disjoint endpoints, so \(m=|E(G)|\) edges use \(2m\) distinct vertices. Hence \(2m\le n\), and, since \(m\) is an integer, \(m\le\lfloor n/2\rfloor\).

For the reverse bound, take \(\lfloor n/2\rfloor\) disjoint edges and, when \(n\) is odd, one isolated vertex. This graph has maximum degree at most one, so it is \(P_3\)-free, and it has exactly \(\lfloor n/2\rfloor\) edges. The upper and lower bounds agree. \(\square\)

Forbidding a Triangle

A triangle-free graph contains no three pairwise adjacent vertices. The relevant local observation is that the neighborhoods of the endpoints of any edge cannot overlap: a shared neighbor would complete a triangle. This observation gives an edge bound, and a complete bipartite graph with balanced parts supplies a construction attaining it.

Proof. Let \(G\) be triangle-free, with \(m\) edges and degrees \(d(v)\). For any edge \(uv\), the neighborhoods \(N(u)\) and \(N(v)\) are disjoint: if a vertex \(w\) belonged to both, then \(uw\), \(vw\), and \(uv\) would form a triangle. Therefore \(d(u)+d(v)\le n\). Summing this inequality over all \(m\) edges gives \(\sum_{v\in V(G)}d(v)^2\le mn\), because a vertex \(v\) contributes \(d(v)\) once for each of its \(d(v)\) incident edges.

Counting edge endpoints gives \(\sum_v d(v)=2m\). Also, \(\sum_v(d(v)-2m/n)^2\ge0\); expanding and using \(\sum_vd(v)=2m\) yields \(\sum_vd(v)^2\ge4m^2/n\). Thus \(4m^2/n\le mn\). If \(m=0\), the claimed bound is immediate. If \(m>0\), dividing by \(m\) and multiplying by \(n/4\) gives \(m\le n^2/4\), and integrality gives \(m\le\lfloor n^2/4\rfloor\).

For attainment, partition the \(n\) vertices into sets of sizes \(\lfloor n/2\rfloor\) and \(\lceil n/2\rceil\), and join every pair with one endpoint in each set, with no edges inside either set. This is a complete bipartite graph: it is triangle-free because a triangle cannot alternate between two parts and return to its starting part. Its number of edges is the product of the part sizes. If \(n=2q\), that product is \(q^2=n^2/4\). If \(n=2q+1\), it is \(q(q+1)=(n^2-1)/4=\lfloor n^2/4\rfloor\). The construction attains the upper bound in both cases. \(\square\)

Forbidding a Three-Leaf Star

The star \(K_{1,3}\) has one centre joined to three leaves. A graph contains it as a subgraph exactly when some vertex has at least three distinct neighbors: select that vertex and any three of those neighbors, and retain the three incident edges. Edges among the selected leaves do not prevent this copy, since the copy need not be induced. Therefore a \(K_{1,3}\)-free graph has maximum degree at most two.

Proof. Let \(G\) be \(K_{1,3}\)-free on \(n\) vertices. Every degree is at most two. Counting each edge at both endpoints gives \(\sum_v d(v)=2m\), so \(2m\le2n\), and hence \(m\le n\). For \(n=1\), a simple graph has no edges, so the maximum is zero. For \(n=2\), simplicity allows at most one edge; the graph \(K_2\), with its two vertices joined by one edge, is \(K_{1,3}\)-free and attains that bound. For \(n\ge3\), the cycle \(C_n\) is simple, has \(n\) edges, and every vertex has degree two. It is \(K_{1,3}\)-free and attains the upper bound \(m\le n\). \(\square\)

For \(n\ge3\), equality in the star-free bound has a useful extra consequence. If \(m=n\), then \(\sum_vd(v)=2n\). Since there are \(n\) vertices and each degree is at most two, every degree must equal two: if even one degree were below two, the sum would be below \(2n\). A finite simple graph in which every vertex has degree two is a disjoint union of cycles. Indeed, following successive edges from any vertex must eventually revisit a vertex because the graph is finite; degree two forces the resulting component to be a cycle. Thus the extremal graphs in this case are precisely the disjoint unions of cycles on at least three vertices.

How to Check an Extremal Answer

These problems illustrate a reliable proof structure. First translate the forbidden subgraph condition into a constraint that can be counted: for \(P_3\), each edge has endpoints not used by another edge; for \(K_3\), neighborhoods across an edge are disjoint; for \(K_{1,3}\), degrees are at most two. Next derive an upper bound valid for every graph satisfying that constraint. Finally, give a graph that satisfies the constraint and has exactly as many edges as the bound allows.

A common mistake is to treat an upper bound as if it already proved the exact extremal number. For example, when \(n=2\), the degree argument for \(K_{1,3}\)-free graphs gives \(m\le n=2\), but that does not imply \(\operatorname{ex}(2,K_{1,3})=2\). A simple graph on two vertices has at most one edge, and \(K_2\), with vertex set \(\{1,2\}\) and edge set \(\{12\}\), is \(K_{1,3}\)-free. Hence the exact value is one. In general, an upper bound needs a matching construction, and a construction alone needs a matching upper bound.

A second pitfall is silently changing “subgraph” to “induced subgraph.” For instance, a triangle contains a \(P_3\) as a subgraph: select two of its edges and omit the third. A triangle is not an induced \(P_3\) on those three vertices, but induced containment is not the condition in \(\operatorname{ex}(n,P_3)\). Reading the forbidden condition precisely is essential before using degrees or counting edges.