3.3. Exercises

  1. Prove that complete graphs have no cut-vertices!
  2. Prove that each nontrivial path contains only two vertices that are not cut-vertices!
  3. Prove that an edge of a graph G is a bridge iff there exist vertices u and w such that e is on every u-w path of G!
  4. Prove that if v is a cut-vertex of a connected graph, then v is not a cut-vertex of .
  5. Prove that every graph containing only even vertices is bridgeless.
  6. Using the definition of a matroid, prove that the Kruskal algorithm finds an economical spanning tree.