I was given the next question:
I'm given an un-directed full graph $G$ with 20 verticals.I need to prove that after removing 18 of the edges the graph is still connected. I tried with induction but failed doing so, any help will be helpful!
p.s.: I'm not allowed to use the Pigeonhole principle.
You can use induction to show
Proposition. Let $G$ be a graph obtained from the complete graph on $n$ vertices by removing at most $\le n-2$ edges. Then $G$ is connected.
Proof. If $n\le 2$, the claim is vacuously true. Assume $n>2$ and let $v$ be any of the vertices of $G$. if $\rho(v)=n-1$, then trivially $G$ is connected. So assume $\rho(v)<n-1$, i.e., at least one of the removed edges ends in $v$. Then the graph $G'$ obtained from $G$ by removing vertex $v$ and its incident edges) has $n-1$ vertices and is the complete graph on these with at most $n-3$ edges removed. By induction hypothesis, it is connected. To show that $G$ is also connected, it suffices to show that there exists at least one edge $vw$ with $w\in G'$, but this follows from $\rho(v)\ge (n-1)-(n-2)=1$. (This last step just barely avoids using the pigeon-hole principle) $\square$