The Extremal Problem for a Three-Vertex Path
Forbidding a graph can impose a very strong restriction on how edges may meet. Here the forbidden graph is the path \(P_3\), which has three vertices and two edges. Because two edges sharing a vertex already form such a path, a graph that avoids \(P_3\) cannot have any vertex incident to two edges. This local restriction determines the entire structure of the graph and makes its maximum possible number of edges exact.
All graphs below are finite and simple. We take \(n\) to be a nonnegative integer, allowing the empty graph on zero vertices. A matching is a set of edges no two of which share an endpoint. A vertex is isolated if it has degree zero. A graph is \(P_3\)-free if it contains no subgraph isomorphic to \(P_3\).
Characterizing the \(P_3\)-Free Graphs
Proof. Suppose first that \(G\) is \(P_3\)-free. If some vertex \(v\) had two distinct neighbors \(u\) and \(w\), then the edges \(uv\) and \(vw\), together with the three distinct vertices \(u,v,w\), would form a subgraph isomorphic to \(P_3\). This contradicts the assumption. Therefore every vertex has degree at most one. In particular, no two edges share an endpoint, so \(E(G)\) is a matching.
Conversely, suppose the edges of \(G\) form a matching. A copy of \(P_3\) would require two edges sharing their middle vertex. No such pair exists in a matching, so \(G\) is \(P_3\)-free. To see the component description, consider any component containing an edge \(uv\). Since the edges form a matching, neither \(u\) nor \(v\) has another incident edge. Thus the component consists exactly of \(u,v\) and the edge \(uv\). Any vertex not in such a component is isolated. This argument also covers the graph with no vertices and graphs with no edges. \(\square\)
The characterization turns the extremal problem into a count of disjoint edges. Each edge in a matching uses two different vertices, and no vertex can be used by two matching edges. Thus at most half the vertices can be paired, with the integer part accounting for an unpaired vertex when \(n\) is odd.
The Exact Formula
Proof. Let \(G\) be any \(P_3\)-free graph on \(n\) vertices. By the characterization, its edges form a matching. If \(G\) has \(m\) edges, those edges use \(2m\) distinct vertices, so \(2m\le n\). Since \(m\) is an integer, \(m\le\lfloor n/2\rfloor\). This proves the upper bound.
For the matching lower bound, take \(n\) vertices and join them in disjoint pairs, leaving one vertex isolated if \(n\) is odd. This graph is a matching, so it is \(P_3\)-free by the characterization. It has \(\lfloor n/2\rfloor\) edges, giving \(\operatorname{ex}(n,P_3)\ge\lfloor n/2\rfloor\). Combining the upper and lower bounds proves the formula.
For the equality statement, a \(P_3\)-free graph attaining the maximum must be a matching with exactly \(\lfloor n/2\rfloor\) edges. If \(n\) is even, these edges use all \(n\) vertices. If \(n\) is odd, they use \(n-1\) vertices and leave exactly one isolated vertex. Conversely, each such matching is \(P_3\)-free and has the stated maximum number of edges. The statement includes \(n=0\): the empty graph has zero edges and is the unique graph on zero vertices. \(\square\)
Worked Example: Classifying a \(P_3\)-Free Graph
Let \(G\) have vertex set \(V=\{1,2,3,4,5,6\}\) and edge set \(E=\{12,34,56\}\). Decide whether it is \(P_3\)-free, and compare its size with the extremal number for six vertices.
The three edges have disjoint endpoints: \(12\) uses vertices \(1,2\), \(34\) uses \(3,4\), and \(56\) uses \(5,6\). Hence the edges form a matching. By the characterization, \(G\) is \(P_3\)-free. Its size is \(|E|=3\). Substituting \(n=6\) into the formula gives \(\lfloor 6/2\rfloor=\lfloor 3\rfloor=3\). Therefore this graph attains \(\operatorname{ex}(6,P_3)=3\).
Check: The degrees of vertices \(1,2,3,4,5,6\) are respectively \(1,1,1,1,1,1\), so no vertex can be the middle vertex of a \(P_3\). Also, the three disjoint edges use \(2\cdot3=6\) vertices, in agreement with the vertex count.
Worked Example: A Five-Vertex Extremal Construction
Construct a \(P_3\)-free graph with as many edges as possible on five vertices, and verify that no \(P_3\)-free graph on those vertices can have more edges.
Set \(V=\{1,2,3,4,5\}\) and \(E=\{12,34\}\). These two edges have no common endpoint, and vertex \(5\) is isolated. Thus the edge set is a matching, so the graph is \(P_3\)-free. It has \(|E|=2\) edges. The formula gives \(\lfloor 5/2\rfloor=\lfloor 2.5\rfloor=2\), so the construction reaches the claimed maximum.
For the upper bound, any \(P_3\)-free graph on five vertices has a matching as its edge set. If it had three edges, those disjoint edges would require \(2\cdot3=6\) distinct vertices, more than the available five. Therefore it has at most two edges. This verifies the maximum directly as well as by the general bound.
Check: The constructed graph has degrees \(1,1,1,1,0\), so every vertex has degree at most one. Its four non-isolated vertices are exactly the endpoints of the two edges, leaving the one required isolated vertex.
Worked Example: Checking the Formula for Small Orders
For each order from zero through four, use a matching construction and compare its edge count with the upper bound. The empty vertex set is included by convention.
| Order \(n\) | Construction | Edge count | Formula value |
|---|---|---|---|
| \(0\) | \(V=\varnothing,\ E=\varnothing\) | \(0\) | \(\lfloor 0/2\rfloor=0\) |
| \(1\) | \(V=\{1\},\ E=\varnothing\) | \(0\) | \(\lfloor 1/2\rfloor=0\) |
| \(2\) | \(V=\{1,2\},\ E=\{12\}\) | \(1\) | \(\lfloor 2/2\rfloor=1\) |
| \(3\) | \(V=\{1,2,3\},\ E=\{12\}\) | \(1\) | \(\lfloor 3/2\rfloor=1\) |
| \(4\) | \(V=\{1,2,3,4\},\ E=\{12,34\}\) | \(2\) | \(\lfloor 4/2\rfloor=2\) |
Each listed edge set is a matching, so every construction is \(P_3\)-free. The edge counts in the third column agree with the formula values in the fourth. For an independent upper-bound check, a matching with \(m\) edges uses \(2m\) vertices: at orders zero and one it can have no edges; at order two it can have at most one; at order three it can still have at most one; and at order four it can have at most two. These bounds agree with the displayed constructions.
Why the Structural Step Matters
The numerical bound depends on the forbidden pattern, not merely on the number of vertices. The argument \(2m\le n\) works here because the edges of a \(P_3\)-free graph are pairwise disjoint. It is not a general rule that every graph with \(m\) edges must use \(2m\) vertices: edges may share endpoints. The characterization must therefore come before the counting step.
Common mistake: counting every edge as if it used two new vertices. On \(V=\{1,2,3,4\}\), take \(E=\{12,13,14\}\). This graph has three edges, whereas \(\lfloor 4/2\rfloor=2\). The tempting statement “three edges need six vertices” is false here because all three edges share vertex \(1\). This graph is not \(P_3\)-free: edges \(12\) and \(13\) form a \(P_3\) on vertices \(2,1,3\). The correction is to establish that a \(P_3\)-free graph has no shared endpoints among its edges, and only then apply the count \(2m\le n\).
There is also a useful distinction between a maximal matching and a matching of maximum size. “Maximal” means that no additional edge can be added to the matching while keeping it a matching; “maximum” means that its number of edges is as large as possible. For this extremal problem, the construction must have \(\lfloor n/2\rfloor\) edges, not merely be maximal. The upper-bound and construction proof establish the maximum directly.
The exact answer is a small but complete example of an extremal method: identify the structural consequence of forbidding a subgraph, count the objects permitted by that structure, and exhibit a graph that meets the bound. Here the forbidden path forces a matching, and pairing as many vertices as possible supplies the matching construction.
Check Your Understanding
Use the characterization and the extremal formula to justify each answer.
- Prove that a graph with maximum degree at most one is \(P_3\)-free.
- For \(V=\{a,b,c,d,e,f,g\}\) and \(E=\{ab,cd,ef\}\), determine whether the graph is \(P_3\)-free and whether it attains the maximum possible size.
- Explain why three pairwise disjoint edges cannot occur in a \(P_3\)-free graph on five vertices.
- Describe the structure of every \(P_3\)-free graph on six vertices that has three edges.
- Give a four-vertex graph with more than \(\lfloor 4/2\rfloor\) edges and identify a copy of \(P_3\) in it.