Skip to main content

Graph Structure and Proof Clinic

Retrieval Prompts​

  1. State the handshaking lemma.
  2. List three equivalent characterizations of a tree.
  3. State the Euler criterion for an Euler circuit.
  4. State one sufficient obstruction to planarity.

Compare and Distinguish​

Separate these pairs:

  • path versus cycle
  • connected versus complete
  • Euler path versus Hamilton path
  • bipartite versus 2-colorable
  • planar drawing versus planar graph

Common Mistake Check​

Explain what is wrong in each claim:

  1. "This drawing has crossings, so the graph is nonplanar."
  2. "The graph has n - 1 edges, so it is automatically a tree."
  3. "All degrees are even, so the graph must have a Hamilton cycle."

Mini Application​

For each graph problem, do all three tasks:

  1. identify the controlling invariant
  2. state the relevant theorem or definition
  3. write a short proof or disproof

Problems:

  1. A graph has 10 vertices, each of degree 3. Can it exist?
  2. Prove that every tree with at least two vertices has at least two leaves.
  3. Decide whether K3,3 is bipartite, planar, both, or neither.
  4. Give an example of a graph with an Euler path but no Euler circuit.

Evidence Check​

This page is complete only if your graph arguments name the correct invariant explicitly: degree sum, parity, unique paths, odd cycles, or planar edge bounds.