Skip to main content

Graph Structure and Proof Clinic

Attempt P12–P20 after lessons 10–18. State finite/simple/undirected hypotheses where required. Feedback includes derivations.

  1. P12: Analyze a triangle plus an isolated vertex. Compute degrees, components and edge count; refute “n−1 edges implies tree.” Then compare a six-cycle with two disjoint triangles to refute degree-sequence sufficiency for isomorphism.
  2. P13: Compute the zero-step and two-step walk matrices for path 0–1–2. Explain why a two-step return walk is not a simple path.
  3. P14: Prove every finite tree on at least two vertices has two leaves using a longest path. Derive m=n−c for a forest with c components, including the empty forest. Explain why rooted and unrooted leaf definitions differ.
  4. P15: For triangle AB=2, BC=2, AC=3, find an MST and compare its root-A distances with shortest-path distances in the original graph. Identify bridges and explain why a spanning tree retains some original non-bridges.
  5. P16: Two triangles share exactly one vertex. Prove an Euler circuit exists and no Hamilton cycle exists. Recheck Euler existence after adding an isolated vertex and after separating the triangles completely.
  6. P17: Count labeled two-colorings of a four-cycle plus one isolated vertex. Prove the minimum color count and then add a cycle diagonal. Supply a short certificate that two colors no longer suffice.
  7. P18: Let L={10,11,12}, R={20,21,22}, eligible pairs (10,20),(11,20), (12,21),(12,22). Find a maximum matching and a Hall-deficient subset proving its optimality. Repair the graph by adding one eligible pair.
  8. P19: Compute faces of a plane forest with n=5,m=3,c=2, including the outer face. Explain what happens to e,f,c when an edge joins components, and when an edge splits a face within a component.
  9. P20: Prove K₅ and K₃,₃ nonplanar using appropriate bounds. Subdivide each edge of K₅ once; calculate n,m, explain why the simple edge bound no longer rules it out, and supply a subdivision obstruction instead.