Let $G(V,E)$ be an un-directed, un-connected graph. Prove that $\bar G$ is connected, And its Diameter is at most $2$.

Question

Let $G(V,E)$ be an un-directed, un-connected graph. Prove that $\bar G$ is connected, and that its diameter is at most $2$.

I've started by writing myself some guidelines:

Two vertices will be neighbors in $\bar G$ if and only if they weren't neighbors at $G$.
Undirected means that exists $u,v\in V$ so there's no track between them.

So I need to prove:

$\bar G$ connected
$\bar G$ diameter is 2 at most.

I guess that for (1) i need to prove that for every $u,v\in V$, I can find a track between them. Or, In some way prove that there are at least $n-1$ edges. And for (2) i just don't know.

So i'm pretty much stuck, I can see the logic behind it [been drawing some examples], But I can't see how can I 'merge' between looking at a vertex in $G$ and then in $\bar G$, I know this might be pretty easy. But i just can't 'see' it.

Thanks.

How is it duplicate? How about the second part of the question? — StationaryTraveller, Jun 26 '13 at 13:36
If you follow my advice to see linked questions, that answer would help realizing that in $\bar G$ the shortest path is at most of the length $2$. — SBF, Jun 26 '13 at 13:38

score 1 · Answer 1 · edited Dec 30 '22 at 18:10

1

This should help

Dr. Math – Connected Graph

edited Dec 30 '22 at 18:10

Glorfindel

3,955

answered Jun 26 '13 at 13:32

Ben Grossmann

225,327

Thanks, That actually really helped for the first part. – StationaryTraveller Jun 26 '13 at 13:37
You can use it for the second part: if you look at the second proof, they explain why there's always a path of length 2 between any two non-adjacent vertices in $\bar G$ – Ben Grossmann Jun 26 '13 at 13:38

Let $G(V,E)$ be an un-directed, un-connected graph. Prove that $\bar G$ is connected, And its Diameter is at most $2$.

1 Answers1