Given a disconnected graph prove that the diameter of its complements is 1 or 2 in witch case is 2.

471 Views Asked by At

I know from another post: Suppose G is disconnected. We want to show that $\overline G$ is connected. So suppose v and w are vertices. If vw is not an edge in G, then it is an edge in $\overline G$, and so we have a path from v to w in $\overline G$. On the other hand, if vw is an edge in G, then this means v and w are in the same component of G. Since G is disconnected, we can find a vertex u in a different component, so that neither uv nor uw is edge of G. Then vuw is a path from v to w in $\overline G$.

This shows that any two vertices in $\overline G$ have a path (in fact a path of length one or two) between them in $\overline G$, so $\overline G$ is connected. So I say that the diameter is 2. When the diameter is 1. Can I have proof with adjacency matrices?

2

There are 2 best solutions below

0
On BEST ANSWER

If the diameter of $\bar{G}$ equals $1$, then for all $u,v\in \bar{G}$ we have $d_{\bar{G}}(u,v)=1$. That is, in $\bar{G}$ all vertices are connected by an edge so that $\bar{G}$ is the complete graph. Thus $G$ must be a graph with zero edges.

From your line of reasoning above, you can also see why this might make sense. You say "On the other hand, if vw is an edge in G, then this means v and w are in the same component of G", and this then gives a path of length $2$. So if there are no such $w,v$ in the same component, we may expect that no paths of length two are needed.

0
On

If you have an edge uv in G, then the distance between u and v is 2 by the proof you have given. So the diameter is 2. Then the only possibility in order to have diameter 1 is that G has no edges.