Turning Graph Definitions Into Proof Obligations

From Definitions to Proof Obligations

A graph statement is easier to prove once its definition has been translated into a list of precise requirements. For example, “\(H\) is a subgraph of \(G\)” requires checking both vertices and edges, while “\(G\) is connected” requires addressing every pair of vertices. In this tutorial, graphs are finite and simple: they have no loops or multiple edges. The goal is to turn these definitions into proof obligations that make clear what must be checked—and what would count as a counterexample.

For a graph \(G=(V,E)\), an edge \(uv\) joins two distinct vertices \(u,v\in V\). A path is a sequence of distinct vertices in which consecutive vertices are joined by an edge; a length-zero path consists of one vertex. The graph \(G\) is connected if it is nonempty and, for every pair of vertices \(u,v\in V\), there is a path from \(u\) to \(v\). A vertex \(x\) is adjacent to \(y\) when \(xy\in E\). These definitions already indicate the quantifiers: connectedness asks for paths for all pairs, whereas adjacency is a condition on one pair.

The last condition is important. A subgraph can omit edges between its chosen vertices; an induced subgraph cannot. In quantified form, for distinct \(u,v\in S\), the induced-subgraph condition is \(uv\in E(G[S])\) exactly when \(uv\in E(G)\). Both directions matter: an edge of \(G\) between vertices in \(S\) must be retained, and an edge in \(G[S]\) must already be an edge of \(G\).

Inclusion and Equality

Proof. The first assertion is precisely the definition of subgraph, so checking those conditions establishes it. For graph equality, equality of graphs means equality of their vertex sets and equality of their edge sets. Each set equality requires both inclusions: \(V(H)\subseteq V(G)\), \(V(G)\subseteq V(H)\), \(E(H)\subseteq E(G)\), and \(E(G)\subseteq E(H)\). Together these give the two set equalities, and hence \(H=G\). Conversely, if \(H=G\), their vertex sets and edge sets are equal by the meaning of graph equality. \(\square\)

This is a useful general pattern: an inclusion claim typically asks you to take an arbitrary element of one set and show it belongs to another. An equality claim asks you to do that in both directions. For edge sets, “take an arbitrary edge” means naming its endpoints and using the definition of an edge or subgraph to justify the required membership.

Proof. Suppose first that \(H=G[S]\). By definition, \(V(H)=S\), and the edges of \(H\) are exactly the edges of \(G\) with both endpoints in \(S\). Thus, for each distinct \(u,v\in S\), \(uv\in E(H)\) if and only if \(uv\in E(G)\). Conversely, suppose \(V(H)=S\) and the stated equivalence holds for every such pair. Every edge of \(H\) then belongs to \(G\), so \(H\) is a subgraph of \(G\). Also, every edge of \(G\) with both endpoints in \(S\) belongs to \(H\), and no other edge of \(H\) exists. Therefore the edge set of \(H\) is exactly the edge set of \(G[S]\), and \(H=G[S]\). If \(S\) has fewer than two vertices, there are no distinct pairs to test; since the graph is simple, there are no edges with both endpoints in \(S\), so the conclusion still holds. \(\square\)

Quantifiers for Adjacency and Connectedness

Definitions involving “every” or “some” should be written with their quantifiers in view. For example, the statement “every vertex of \(G\) has a neighbor” means that for every \(v\in V(G)\), there exists a vertex \(u\in V(G)\) such that \(uv\in E(G)\). The order of the quantifiers matters. “There is a vertex adjacent to every other vertex” instead means that there exists \(x\in V(G)\) such that for every \(v\in V(G)\) with \(v\ne x\), \(xv\in E(G)\).

Connectedness has the same “for every pair” structure. A helpful equivalent test is to choose one vertex and find paths from it to all the others. The following result justifies that reduction.

Proof. Suppose \(G\) is connected. Choose any \(r\in V(G)\), which is possible because \(G\) is nonempty. By connectedness, every vertex \(v\in V(G)\) has a path to \(r\). Conversely, suppose there is such a vertex \(r\). For any \(u,v\in V(G)\), take a path from \(u\) to \(r\) and a path from \(r\) to \(v\). Joining these sequences gives a walk from \(u\) to \(v\), possibly with repeated vertices. If a walk repeats a vertex, delete the part of the sequence between two occurrences of that vertex; the remaining sequence is still a walk with the same endpoints and has shorter length. Repeating this deletion finitely many times produces a path. Thus every pair \(u,v\) has a path, so \(G\) is connected. When \(G\) has one vertex, that vertex has a length-zero path to itself, and the argument applies. The empty graph is excluded by the stated nonempty hypothesis. \(\square\)

Universal Claims and Counterexamples

A universal claim says that a property holds for every object in its stated range. To prove it, begin with an arbitrary object satisfying the hypotheses and establish the conclusion without relying on a special feature of that object. To refute it, one counterexample in the stated range is enough. A precise negation is useful: “for every graph \(G\), \(P(G)\)” is false if there exists a graph \(G\) for which \(P(G)\) fails.

Quantifier order also helps distinguish a universal vertex from a statement that every vertex has a neighbor. In the example, every vertex does have a neighbor, but there is no one vertex adjacent to every other vertex. Conversely, an edgeless graph with two vertices has no vertex with a neighbor. A claim about all graphs must account for such boundary cases if they fall within its hypotheses.

Common Pitfalls

Checking only one inclusion when proving equality. Suppose \(E(H)\subseteq E(G)\). This establishes only that \(H\) has no edge outside \(G\); it does not show that \(H\) contains every edge of \(G\) that it should contain. For an induced subgraph on \(S\), the missing obligation is to check that every edge of \(G\) with both endpoints in \(S\) is retained.

Replacing “every” with “some.” To prove connectedness, finding a path between one pair of vertices is not enough. The definition requires a path for every pair. The fixed-vertex criterion reduces the work, but it still requires paths from that vertex to all vertices.

Using a picture instead of a definition-based check. A drawing can suggest adjacency or connectedness, but the proof should refer to the stated vertex and edge sets. In the connectedness example, each path is justified by checking its consecutive pairs against the edge set.