Let $G = \langle V, E \rangle$ be a simple graph such that $|V| = 7$ and $|E| = 16$.
Denote the number of G's components by $\alpha$. Is it necessary that $\alpha = 1$?
I think that the statement is indeed true - by observing the complete graph $K_{7}$ which represents the most simple scenario (.i.e G is $K_{7}$), it seems intuitively that I could find a path between any two vertices on the complete graph after "removing" the five edges too. However, my struggle is in formalizing it\find the cases which I need to observe between.
Obviously that one case is when there exists some $v \in V$ which satisfies $deg(v) = 6$. Otherwise, I claimed that each vertex is at least of degree 1 and since $|V|$ is odd, by the Handshaking lemma we get that there is some $u\in V$ s.t $deg(v) \in$ {$2, 4$}. But still, I don't see how it leads into a contradiction.
I'd like for some clarification/ideas, thanks.