3.3. Exercises
- Prove that complete graphs have no cut-vertices!
- Prove that each nontrivial path contains only two vertices that are not cut-vertices!
- 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!
- Prove that if v is a cut-vertex of a connected graph, then v is not a cut-vertex of .
- Prove that every graph containing only even vertices is bridgeless.
- Using the definition of a matroid, prove that the Kruskal algorithm finds an economical spanning tree.