Question about maximal connected subgraph [closed]

A maximal connected subgraph of G is a connected subgraph of G that is maximal with respect to the property of connectedness. This is called a component of G. Visually, components of G are the pieces of G that add up to make G.

Let me briefly explain each of the terms.

Let G=(V,E) be a (simple) graph. A subgraph H of G is connected if, for every pair of distinct vertices u, v in H, there exists a u−v path in H.

A connected subgraph H is maximal provided H is not properly contained in a connected subgraph of G. In other words, H is a maximal connected subgraph of G if H is a subgraph of H′ and H′ is a connected subgraph of G, then H=H′.

How can I show that the maximal connected subgraphs of a graph are its components?


Let $C$ be a component of $G$. We'll use the definition that for all $a,b \in V(C)$, there exists a path from $a$ to $b$ in $C$, and for all $v \in V(G)\setminus V(C)$, there exists no path from $a$ to $v$ (1). Assume for the purposes of contradiction that $C$ is properly contained in another connected induced subgraph $H$ of $G$. Then there exists some $h \in V(G)$ such that $h \in V(H)$ but $h \not \in V(C)$. Since $C$ is contained in $H$, we know that $a \in V(H)$. Since $H$ is connected, we know that there exists a path from $a$ to $h$ in $H$. But $h \in V(G)\setminus V(C)$, so the existence of this path contradicts our prior conclusion (1). Thus our assumption of the existence of $H$ was false.