Proof. Theory graph. Please check.

Question

If graph $G = (V,E) $ where $|V| = n $ is connectivity then $ n-1 \le |E| $

My proof:

The our thesis is:

$ \forall G $ is connectivity $\Rightarrow$ $ n-1 \le |E| $

I prove that using 'reductio ad absurdum' $\neg (\forall G \mbox{ is connectivity }\Rightarrow n-1 \le |E| ) \iff |E| < n -1 \Rightarrow \exists G \mbox{ non-connectivity. }$ So, I proved that exists verticle $v$, such $deg(v) = 1$ It's obvious, so I don't present my proof.

Because of the there is verticle $v$ such $deg(v) = 1$ removing one edge it can make that graph will become non-connectivity. This proof is OK? Why? Why not?

Answer 1

If you have learned about trees, it may be helpful to use them here. Note that a tree is a minimally connected graph. A tree $T$ has $V - 1$ edges, and every edge is a cut edge. That is, if you remove an edge from $T$, you disconnect the graph. Leveraging trees will make your proof pretty straight-forward.

Answer 2

The proof is somewhat flawed. First, the "it's obvious" part might apply to the whole proof; it depends on who is reading it. Given your proof skills, and the fact that you're evidently trying to learn to do proofs, you might want to write out that "obvious" part.

I also suggest that you treat $G$ as a given: the contrapositive (not "reductio ad absurdum") is then "$|E| < n-1$ implies $G$ is not connected." You don't have to prove the existence of $G$ -- just show that any $G$ for which this is true cannot be connected.

You manage to conclude that for some vertex of $G$, $deg(v) = 1$. But that doesn't make $G$ disconnected at all. Consider the following $2$-node graph, with one edge: o-----o. Both vertices have degree 1, but the graph is not disconnected.

So: give it another try, and let's see what you come up with.