# 3

Let $G$ be a simple graph such that $\mathrm{diam}(G) \geq 3$. Then $\mathrm{diam}(G^c) \leq 3$. Moreover, if $\mathrm{diam(G)} > 3$ then $\mathrm{diam}(G^c) < 3$.

Reminders: $G^c$ is the complement graph,  so $V(G) = V(G^c)$ and $e \in E(G^c) \iff e \not \in E(G)$. $\displaystyle \mathrm{diam(G)} = \max_{v_i, v_j \in V(G)} d(v_i, v_j)$. For example, $\mathrm{diam}(K_n) = 1$.

## One thought on “3”

1. gciruelos says:

Let $u,v$ be two vertices in $G$ such that $d(u,v) \geq 3$ and let $x,y$ be any two vertices of $G$. Then $x$ is adjacent to at most one of $u,v$, because otherwise we would have a path of length 2 between $u$ and $v$. The same happens to $y$.
WLOG we assume that $x$ is not adjacent to $v$ in $G$. If $y$ is also not adjacent with $v$ then $xvy$ is a path of length 2 in $G^c$.
If $y$ is adjacent to $v$ in $G$ then $y$ is not adjacent to $u$ in $G$ and then $xvuy$ is a path of length 3 in $G^c$.

We have shown that any two vertices $x,y$ of $G^c$ are at distance $\leq 3$.

For the second part, assume the contrary and use the first part, noting that $G^{c^c} = G$.

Like