Graph Theory: 54. Number of Cut-Vertices

Notice that the complete graph on n vertices has no cut-vertices, whereas the path on n vertices (where n is at least 3) has n-2 cut-vertices. Can you ever have a connected graph with more than n-2 cut-vertices? The answer is no. We prove that in any non-trivial connected graph there are at least 2 non-cut-vertices. In fact, the proof shows that peripheral vertices of a graph are not cut-vertices.
-- Bits of Graph Theory by Dr. Sarada Herke.



Related videos:
   • Graph Theory: 53. Cut-Vertices   - 53 cut-vertices
   • Graph Theory: 51. Eccentricity, Radiu...   - 51 eccentricity, radius and diameter

For quick videos about Math tips and useful facts, check out my other channel
"Spoonful of Maths" -    / spoonfulofmaths