Proof-Strategy Workshop With Small Graphs

Choosing a Strategy Before Writing a Proof

A graph problem can often be approached in several ways, but a proof strategy is useful only when its steps match the structure of the claim. If removing a vertex leaves a smaller object of the same kind, induction may fit. If the claim concerns a largest or smallest object, choosing one that is extremal can expose a useful constraint. If the same collection can be counted in two ways, double counting may turn a local description into an identity. If a proposed counterexample can be reduced while retaining its failure, a minimal-counterexample argument may force strong local conditions.

This workshop develops those choices through four small problems. The examples use finite simple graphs. A subgraph is formed by taking some vertices and some edges between them; it need not be induced. An independent set is a set of vertices no two of which are adjacent. A forest is a graph with no cycle. The degree of a vertex is its number of neighbors, and \(\Delta(G)\) is the largest degree in \(G\). These definitions will be enough for the arguments below.

In each case, choosing a strategy is only the beginning. One must verify that the reduced graph satisfies the needed hypothesis, or that the counted objects are counted with exactly the stated multiplicity. The calculations that follow make those checks explicit.

Induction: Edge Counts in Forests

Proof. We use induction on \(n\). When \(n=0\), the graph has no edges and no components, so \(m=0=n-c\). Now suppose \(n\ge1\), and assume the statement holds for every forest with fewer than \(n\) vertices. A nonempty forest has either an isolated vertex or a vertex of degree one: if some component has at least two vertices, take a path of maximum length in that component. An endpoint cannot have a neighbor outside the path, since that would extend the path, and cannot have another neighbor on the path, since that would create a cycle. Thus that endpoint has degree one. If every component is a single vertex, there is an isolated vertex instead.

If \(v\) is isolated, deleting it gives a forest with \(n-1\) vertices, \(m\) edges, and \(c-1\) components. The induction hypothesis gives \(m=(n-1)-(c-1)=n-c\). If \(v\) has degree one, deleting it removes exactly one edge and does not change the number of components: its neighbor remains in the same component, and no other vertex loses a connection through \(v\), which had only one neighbor. The smaller forest has \(n-1\) vertices, \(m-1\) edges, and \(c\) components. Therefore \(m-1=(n-1)-c\), which rearranges to \(m=n-c\). Both cases establish the formula. \(\square\)

Induction fits because the class of forests is preserved by deleting a vertex, and the change in \(n,m,c\) can be calculated exactly. An argument that simply says “remove a vertex” would not suffice: deleting an arbitrary vertex can remove several edges and can change the component count in more complicated ways. The proof selects a vertex whose effect is controlled.

Extremal Selection: A Guaranteed Independent Set

Proof. Choose an independent set \(S\) of maximum size; one exists because the graph has finitely many vertex subsets. Every vertex outside \(S\) has a neighbor in \(S\), since otherwise it could be added to \(S\), contradicting maximal size. For \(s\in S\), let its closed neighborhood be \(N[s]=\{s\}\cup N(s)\). The closed neighborhoods of the vertices in \(S\) therefore cover \(V(G)\). Consequently,

Since \(\Delta(G)+1>0\), division gives \(|S|\ge n/(\Delta(G)+1)\), as required. \(\square\)

Here the extremal choice supplies the key property: a maximum independent set is also maximal, meaning no vertex can be added to it. A direct attempt to choose vertices one by one may find a large independent set, but without controlling which vertices remain available it does not by itself prove this bound. The covering argument explains why the maximum degree controls the guarantee.

Double Counting: Triangles Through Their Edges

Proof. Count pairs consisting of an edge \(uv\) and a vertex \(w\) adjacent to both \(u\) and \(v\). For a fixed edge \(uv\), the number of such pairs is the number of common neighbors of its endpoints, so counting by edges gives the stated sum. Each such pair determines a triangle with vertices \(u,v,w\). Conversely, every triangle contributes one such pair for each of its three edges, and contributes no other pairs. Thus each triangle is counted exactly three times, proving the identity. \(\square\)

Double counting works here because the objects have two precise descriptions: an edge with a common neighbor, or a triangle together with one of its edges. A common error is to equate the sum directly to the number of triangles. In this example that would give \(6=2\), which is false. Each triangle contributes three times, not once.

Minimal Counterexample: A Subgraph with Large Minimum Degree

Proof. If \(d(G)=0\), the graph has no edges, and any one-vertex subgraph has minimum degree \(0\), so the claim holds. Suppose \(d(G)>0\), and assume for contradiction that some graph satisfying the claim’s hypotheses has no such subgraph. Choose a counterexample with the fewest vertices. Write \(d=d(G)>0\) and \(m=|E(G)|\), so \(2m/n=d\).

If every vertex has degree at least \(d/2\), then \(G\) itself is a nonempty subgraph with the required minimum degree, contradicting that \(G\) is a counterexample. Therefore some vertex \(v\) has \(\deg(v)<d/2\). The graph \(G-v\) is nonempty: a one-vertex graph has average degree \(0\), contrary to \(d>0\). It has \(n-1\) vertices and \(m-\deg(v)\) edges. Its average degree is

The strict inequality uses \(\deg(v)<d/2\), and the equality uses \(2m=nd\). Thus \(G-v\) has average degree at least \(d\), so it is another graph to which the theorem applies. It has fewer vertices than \(G\); by the minimal choice of \(G\), it contains a nonempty subgraph of minimum degree at least half its own average degree. That degree is greater than \(d/2\), so the same subgraph also certifies the theorem for \(G\), a contradiction. Hence no counterexample exists. \(\square\)

This proof uses minimality to justify the reduction: after deleting a vertex of degree below half the original average, the average degree increases, so the smaller graph still meets the hypothesis. Merely choosing a vertex of low degree does not finish the argument; the calculation showing that the reduced graph remains eligible is essential. Induction could also be considered, but the minimal-counterexample formulation makes the contradiction especially direct: a smaller eligible counterexample is impossible by the choice of the original one.

How to Check a Strategy

Before committing to a proof, identify the object that changes and calculate what the change does to the hypotheses. For induction, state the parameter that decreases and verify the base case. For an extremal choice, state exactly what is largest or smallest and derive the consequence of improving it. For double counting, define the objects being counted and check the multiplicity from both viewpoints. For a minimal counterexample, specify the measure of minimality and show that the reduction preserves the claim’s assumptions.

A method can be valid in principle without being the most direct one. For example, the triangle identity is naturally a double count; deleting vertices does not immediately explain why every triangle contributes exactly three times. The independent-set bound depends on a maximality consequence and a covering estimate, not on counting all graph edges. In the forest formula, arbitrary deletion obscures the component changes, while a leaf or isolated vertex makes them manageable. The central discipline is not to name a strategy, but to supply the check that makes its key step work.