14
$\begingroup$

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

What I was thinking about:

$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$).

$\endgroup$
7
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

X can be adjacent to

  • 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.

$\endgroup$
-1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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