# If the diameter of graph is greater than 3 then the diameter of its complement graph is less than 3

Graph $G$ has the diameter greater than $3$. Prove that the diameter of $G'$ (the complement graph) is less than $3$.

$G$ has the diameter greater than $3$ $\implies$ $G$ has not less than $4$ vertices.

If the $u$ and $v$ are vertices in $G$ that represents the diameter, then in $G'$ there is the edge $uv$. So, I was thinking that only first neighbors can be the diameter of $G'$. We need to prove now that between every two neighbors in $G$ there is only one other vertex in $G'$ which connects these two vertices (so the diameter is less than $3$).

Denote distance in $G$ by $d$ and distance in $G'$ by $d'$. Define $u,v$ as you did, so that $d(u,v) \ge 4$. We wish to show for any vertices $x,y$, that $d'(x,y) \le 2$.

Among $x, y, u, v$ there are at most four distinct vertices. In particular, since $d(u,v) \ge 4$, $u$ and $v$ cannot be connected by a path among $x,y,u,v$. So it is possible to split $x,y,u,v$ into two components which are not connected in $G$, one containing $u$ and one containing $v$. WLOG we may assume the components are $\{u,x\}, \{v,y\}$ or $\{u,x,y\}, \{v\}$.

• In the first case, $x$ and $y$ have no edge in $G$, so they have an edge in $G'$ and $d'(x,y) = 1$.

• In the second case, $x$ and $y$ are both connected to $v$ in $G'$, so $d'(x,y) \le d'(x,v) + d'(y,v) = 2$.

Thus $d'(x,y) \le 2$ for any $x,y$, proving that $\operatorname{diam} G' \le 2$.

Denote by $d_G$ and $d_{G'}$ the distances in $G$ and $G'$, respectively. Take vertices $u,v$. There are a few cases of interest.

If $d_G(u,v)\geq 2$, then the edge $uv$ is not in $G$, so $uv\in G'$ and thus $d_{G'}(u,v)=1$.

Now suppose $d_G(u,v)=1$. Take other vertices $p,q$ with $d_G(p,q)\geq 3$ (this must exist as diameter $\geq 3$), so in particular one of $p$ or $q$ is not connected to $u$. Similarly, one of $p$ and $q$ is not connected to $v$. There are two cases:

Both $u$ and $v$ are not connected (in $G$) to the same vertex, say $p$. Then $upv$ is a path of length $2$ in $G'$ from $u$ to $v$ and thus $d_{G'}(u,v)=2$.

$u$ is not connected to $p$ and $v$ is not connected to $q$ (or vice-versa). Since $p$ is also not connected to $q$, we have a path $upqv$ in $G'$ from $u$ to $v$ and thus $d_{G'}(u,v)\leq 3$.

Therefore, $G'$ has diameter at most $3$.

Given any graph $G,$ choose vertices $x,y,u,v$ such that $d_G(x,y)=\operatorname{diam}(G)$ and $d_{G'}(u,v)=\operatorname{diam}(G').$ Let $H$ be the subgraph of $G$ induced by $\{x,y,u,v\}.$ Then $$\operatorname{diam}(G)=d_G(x,y)\le d_H(x,y)\le\operatorname{diam}(H)$$ and $$\operatorname{diam}(G')=d_{G'}(u,v)\le d_{H'}(u,v)\le\operatorname{diam}(H').$$ That is, any graph $G$ has a subgraph $H$ of order $\le4$ such that $\operatorname{diam}(G)\le\operatorname{diam}(H)$ and $\operatorname{diam}(G')\le\operatorname{diam}(H').$ Therefore, in order to show that the statement $$\operatorname{diam}(G)\le3\ \ \text{ or }\ \operatorname{diam}(G')\le2$$ holds for all graphs, it will suffice to show that it holds for all graphs of order $\le4.$ As there are only a few nonisomorphic graphs of order $\le4,$ this is Quite Easily Done.

I will present my answer to a little more general question :

If G be a graph with diameter(G) $\geq$ 3. Prove that the diameter(G′) $\leq$ 3. where G' is the complement graph.

This answer is similar to @Luiz answer but little bit more explained as it took me quite a time to understand that answer.

So, let's begin.

What is given to us ?
G be a graph with diameter(G) ≥ 3 .

Let the diameter be from some vertex $P$ and $Q$. It will look something like this :

$P$_________$V1$_______$V2$________...... ________$Q$

What more can we conclude ?

We easily see that $P$ and $Q$ cannot have a common adjacent vertex. Why ? Let $L$ be the common adjacent vertex to both to $P$ and $Q$ , then path $PLQ$ is the shortest path from $P$ to $Q$.

But this path is of length of 2. If the diameter is from some vertex $P$ and $Q$ and diameter(G) $\geq$ 3 , then path $PLQ$ cannot exist. Hence no such $L$ exist.

So, we conclude that if

$P$_________$V1$_______$V2$________...... ________$Q$

is our diameter in $G$, then $P$ and $Q$ cannot have common adjacent vertex.

Now, let us come back to our question. What we will do is we will try to find the the shortest path length between any 2 vertex in $G'$ say , $X$ and $Y$.

Hence , let $X$ and $Y$ be any 2 randomly chosen vertex ($X$$\neq$ $Y$) from G

Now two cases arise :

Case 1 : In Graph $G$ , X and Y are not adjacent.

This means that in G' , X and Y will be adjacent. Hence , Shortest path from X to Y is 1.

Case 2 : In Graph $G$ , X and Y are adjacent.

This means that in G' , X and Y will not be adjacent. Now , what ? Well if X and Y are not adjacent , 2 more sub-cases can arise :

a) X and Y are unreachable in G' That is we can never reach Y from X or vice versa. If that we case , such pair of X and Y are useless for calculating the diameter(G'). Hence we ignore them.

b) X and Y are reachable in G' This is interesting case and the only case left. We will see shortly that such X and Y shortest path can be either 2 or 3 in length but never more than that in G'. Hence , from Case 1 and Case 2 we will conclude that diameter(G') $\leq$ 3. So, let's deep dive into this now and be done with proof.

Remember P and Q above - the endpoints of our diameter in G. Now we are going to see that if X and Y are reachable, then I can always construct a path from X to reach Y with has length either 2 or 3 in G' using the vertex P and vertex Q. Clearly then, shortest distance between X and Y will always be $\leq$ 3.This is how we will complete the proof.

So, few sub cases arise again. (I know lot of sub cases to consider in this answer but then i am deliberately trying to be explicit in explainig each case. )

Remember now that P and Q cannot be have common adjacent vertex ever in G. This is very important fact. We will be using it now.

Also, note that there P and Q will be adjacent to each other in G'. ( The diameter(G) >=3 . This means that in G , between P and Q, we have at least 2 vertex and shortest path from P to q is through them. Hence, in G , P and Q are not adjacent, which makes them adjacent in G')

So, what do you think ? How can X and Y be related to P and Q in G'? What all be possible cases ? Well, let's see.

• only P or
• to only Q or
• adjacent to P and Q both or
• X might not be adjacent to P and Q both.

Similarly, Y can be

• only P or
• to only Q or
• adjacent to P and Q both or
• Y not be adjacent to P and Q both.

We will now have to see combinations together one by one. We see, there can be 16 combinations like :

Combination 1 : X adjacent to only P AND Y adjacent to only P Clearly , shortest path to reach from X to Y <= |XPY| = 2.

Combination 2 : X adjacent to only Q AND Y adjacent to only Q Clearly , shortest path to reach from X to Y <= |XQY| = 2.

Combination 3 : X adjacent to only P AND Y adjacent to only Q Consider the path XPQY. This has length 3. Connects X and Y. [Note that in G' , P and Q are adjacent.] Clearly, shortest path to reach from X to Y <= |XPQY| = 3.

Combination 4 : X adjacent to only Q AND Y adjacent to only P Consider the path XQPY. This has length 3. Connects X and Y. [Note that in G' , P and Q are adjacent.] Clearly, shortest path to reach from X to Y <= |XQPY| = 3.

Combination 5 : (X not adjacent to P and Q) AND (Y adjacent to only P) This is interesting. if X not adjacent to P and Q in G', then X was adjacent to P and Q in G. This is contradiction as we proved above - In G , P and Q cannot have common adjacent vertex.

Combination 6 : (X not adjacent to P and Q) AND (Y is adjacent to only Q) Same as above. If X not adjacent to P and Q in G', then X was adjacent to P and Q in G. This is contradiction as we proved above - In G , P and Q cannot have common adjacent vertex.

Combination 7 : (X adjacent to only P) AND (Y not adjacent to P and Q) Similar as above. If Y not adjacent to P and Q in G', then Y was adjacent to P and Q in G. This is contradiction as we proved above - In G , P and Q cannot have common adjacent vertex.

Combination 8 : (X adjacent to only Q) AND (Y not adjacent to P and Q) Same as above. If Y not adjacent to P and Q in G', then Y was adjacent to P and Q in G. This is contradiction as we proved above - In G , P and Q cannot have common adjacent vertex.

Combination 9 : (X not adjacent to P and Q) AND (Y not adjacent to P and Q) Same as above. If X, Y not adjacent to P and Q in G', then X and Y was adjacent to P and Q in G. This is contradiction as we proved above - In G , P and Q cannot have common adjacent vertex.

It's easy to see the rest 7 cases. Tell me if it is not clear. I will add more details.

Note : We could have reduced these 16 cases to only 4 by combining them to :

X can be

• connected to P or Q or both.
• Not connected to P and Q

Similarly for Y.

But for newbies like me , I tried to give detailed explanation.

This completes our proof.

Let $G$ and $G'$ to denote the graph and its complement. Let {u,v} be any pair of vertices of the graph G. If uv is not an edge in G, then uv is an edge in G' and so $d'(u,v)=1$. On the other hand, if $uv$ is an edge in $G$, then there must be a vertex in $G$, say $w$, which is not adjacent to both u and v; since otherwise $diam(G)\le 3$, which is impossible. Therefore, $d(u,v)=2$.