Is a simple graph connected, if every node has at least one adjacent edge and $|E|\ge |V|-1$?

cs.stackexchange https://cs.stackexchange.com/questions/112319

  •  05-11-2019
  •  | 
  •  

Question

Let $G=(V,E)$ be an undirected graph without self-loops or parallel edges.

Is the following statement true?
If $|V|=n, |E|\ge n-1$ and every node has at least one adjacent edge, then $G$ is connected.

I've proved it for $|E|=n-1$:

Per induction:
Start:
For $\left|V\right|=1$ the graph is trivially connected.

Induction step:
Let the statement be shown for all graphs $G=\left(V,E\right)$ where $\left|V\right|=n-1$ and $|E| = n-2$.

Let further $G=\left(V,E\right)$ with $\left|V\right|=n$ and $|E| = n-1$ be given.

We're now looking for an induced sub graph $G|_{V^\prime}$ where $V^\prime\subset V, \left|V^\prime\right|=n-1$, so that $G|_{V^\prime}$ has at least $n-2$ edges.

(Any such sub graph can have at most $n-2 $ edges, as there'll always be at least one edge that originally lead to the removed node)

Let's now assume that every sub graph $G|_{V^\prime}$ has less than $n-2$ edges.
Then, the removed node in any sub graph would have at least $2$ edges.

Thus, every node must have at least $2$ edges, and therefore there'd have to exist at least $n$ edges in the graph.

Therefore, there's at least one sub graph $G|_{V^\prime}$ with $n-2$ edges, for which our induction assumption holds. And because there is one edge from $G|_{V^\prime}$ to the erased edge, we get that $G$ is connected.

Therefore, the induction is completed.

However, if I try to generalize the above proof, the same style leads to an inequality that only holds if $|E|>|V|$.

Therefore, if the above proof can be generalized, how would it look? If not, what's an example where it fails?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top