Show that if $H$ is a spanning subgraph of a non complete graph $G$ then $t(H) \leq t(G)$

66 Views Asked by At

Show that if $H$ is a spanning subgraph of a non complete graph $G$ then $t(H) \leq t(G)$

Since $H$ is a spanning subgraph of a non complete graph $G$, $V(H) = V(G)$ and $E(H) \subset E(G)$, so every cut vertex of $G$ is cut vertex of $H$.

if $H$ is disconnected then $t(H)=0$ and we are done.

if $H=G$ then $t(H)=t(G)$

if $H \ne G$ then $S_H$ will be proper subset of $S_G$, so $t(H)<t(G)$

I feel like my reasoning sound a little bit too awkward. I wonder if there is a way to make it flow smoothier?