2
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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

No, it is not true. Here is an counterexample.

A counterexample to https://cs.stackexchange.com/questions/112319/ made at http://graphonline.ru/en/?graph=PagrELGyBoCzlfaD

Graph made at https://graphonline.ru/en/

Exercise. Construct a simpler counterexample where $|V|=n$ and $|E|=n-1$.

$\endgroup$
1
  • $\begingroup$ Thanks for the enlightening example! I knew something was fishy, but even with the example at hand it took me quite some time to get that I forgot to check that "every node has an adjacent edge" property $\endgroup$
    – Sudix
    Jul 31, 2019 at 2:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.