Recipe

Test whether vertex and edge counts are consistent with a tree

Use when: you know a connected graph's vertex count and edge count and need to decide whether they are consistent with the graph being a tree

Goal: a verdict on whether the counts rule out a tree, confirm the necessary count, or still require a direct check

Taught in Properties of trees

1. 1

   For n vertices, compute n - 1; this is the exact edge count every tree on n vertices has.

   Example

   A tree has 41 vertices, so the required count is 41 - 1 = 40 edges.

   Why: the tree edge-count theorem fixes this number exactly, with no exceptions, for every tree.

2. 2

   Compare the given edge count to n - 1 from Step 1.

   Example

   A connected graph has 10 vertices and 11 edges. The required count is 10 - 1 = 9, but the graph has 11, two more than that.

   • actual edges are greater than n-1 — the graph must contain a cycle, so it cannot be a tree; stop here.
   • actual edges are fewer than n-1 — the graph cannot reach every vertex, so it cannot be a tree; stop here.
   • actual edges equal n-1 — the count matches, but continue to Step 3 before concluding anything.

   Why: a connected graph with more than n-1 edges must contain a cycle, and one with fewer edges cannot connect every vertex, so only a matching count leaves the question open.

3. 3

   A matching edge count is necessary for a tree, but not sufficient by itself; verify separately that the graph is connected and has no cycle.

   Example

   A graph has 6 vertices and 5 edges, matching 6-1=5. But a 5-vertex cycle together with 1 isolated vertex also has 6 vertices and 5 edges, and that graph is disconnected and contains a cycle.

   Why: two different graphs can share the same edge count while only one of them is actually a tree, so the count alone never finishes the argument.