Been struggling with this home-work question for some days now. Will appreciate an explanation.
Let $c(G)$ denote the amount of connected components in a graph $G$.
a. prove that $\forall e\in E: c(G) \leq c(G-e) \leq c(G)+1$
b. show that there is a graph $G$ with a vertex $v$ such that $c(G-v) \geq c(G)+1$
I'm kinda new to this all graph-theory subject so I so kinda lost on how to get started as well. Any help will be much appreciated.
Suppose $e=\{a, b\}$ is in connected component $A$ of $G$. you need to show that:
Connected components of $G$ other than $A$ will remain connected components of $G-e$.
Every vertex in $A$ can be joint to either $a$ or $b$ using edges in $A - e$. so each vertex of $A - e$ will be in either $a$'s or $b$'s respective connected component.
for part b of your question, think of a star!