# A Note on Graph Connectivity :author: { :name: Prof. Alice Mathematician :affiliation: Institute of Pure Mathematics } :: :abstract: We present a short proof of a classical result in graph theory, demonstrating RSM's structured proof capabilities. :: ## Introduction :let: $G = (V, E)$ be an undirected graph::. We say $G$ is **connected** if there exists a path between any two vertices. :definition: { :label: def-component } A **connected component** of $G$ is a maximal connected subgraph. :: ## Main Result :theorem: { :title: Component Bound :label: thm-main } :let: $G$ be a graph with $n$ vertices and $m$ edges::. Then :claim:{:label:goal} $G$ has at most $n - m$ connected components::. :: :proof: :step: {:label:base-case} For the base case, :assume: $m = 0$ (no edges)::. :p: Then each vertex is its own component, so there are exactly $n$ components. The bound holds with equality. :: :: :step: {:label:induction-step} For the inductive step, :assume: the theorem holds for graphs with $m - 1$ edges::. :p: :step: :let: $e = \{u, v\}$ be any edge in $G$::, and :write: $G' := G - e$ for the graph with $e$ removed::. :: :step: By the induction hypothesis, $G'$ has at most $n - (m-1) = n - m + 1$ components. :: :step: Adding $e$ back either merges two components (decreasing the count by 1) or leaves the count unchanged. :: :step: Therefore, $G$ has at most $(n - m + 1) - 1 = n - m$ components. :: :: :: :step: :ref:goal, The claim:: follows by induction. :qed: :: :: ## Remarks The bound in :ref:thm-main:: is tight: the complete graph on $n$ vertices achieves equality when $m = \binom{n}{2}$.