[Math] Diameter of a Connected Graph

combinatoricsgraph theory

Problem

  1. Prove that if $G$ is connected and $\text{ diam}(G) \geq 3$, then $\overline{G}$ is connected.
  2. Prove that if $\text{ diam}(G) \geq 3$, then $\text{ diam}(\overline{G}) \leq 3.$
  3. Prove that if $G$ is regular and $\text{ diam}(G) = 3$, then $\text{ diam}(\overline{G}) = 2$.

Approach

I tried to find relationships between the diameters of $G$ and $\overline{G}$, but all I could think of was the effect of adding edges to the graph reduces the diameter in most cases, but not necessarily.

Any help would be greatly appreciated!

Best Answer

(1) Let $G$ be a connected graph. Suppose $\bar{G}$ (the complement of $G$) be disconnected. We shall prove that $G$ has $diam(G)\le 2$. (hence, proving the claim by contra-positive)

Let $C_1,C_2,\dots C_n$ be connected components of $\bar{G}$. Since, $\bar{G}$ is disconnected, there are at least two connected components. In $G$,

  1. there is an edge between any two vertices that belong to different connected components of $\bar{G}$.
  2. For any two vertices belonging to a connected component of $\bar{G}$, there is a path connecting them via a vertex belonging to a different connecting component.

Hence, $diam(G)\le 2$. The case of $diam(G)=1$ occurs when $\bar{G}$ has no edges at all.

(2) Let $diam(G)\ge 3$. If $G$ is disconnected, then $\bar{G}$ is connected with $diam(\bar{G})=2$ (from 1). Suppose, G is connected and $diam(G)=k\ge 3$. Let $v_1$ and $v_{k+1}$ be two vertives of $G$ connected via shortest path of length $k$. Let $L_r:=\{v \mid \, \text{ length of the shortest path between } v_1 \text{ and } v \text{ is } r, 1\le r\le k-1\}$. Since, $v_{k+1}$ exists, $L_r\ne \emptyset \, ,\, \forall \, 1\le r\le k-1$.

In $\bar{G}$,

  1. $v_1$ is connected to $v_{k+1}$ via an edge.
  2. $v_1$ is connected to any element of $L_r$ where $2\le r\le k-1$ via an edge.($v_{k+1}$ is connected to any element of $L_r$ where $1\le r\le k-2$ via an edge)
  3. $v_1$ is connected to any element of $L_1$ via $v_{k+1}$. ($v_{k+1}$ is connected to any element of $L_{k-1}$ via $v_{1}$)
  4. Let $1\le i\le k-1$ and $1\le j\le k-1$. If $\mid i-j \mid>1$, any two vertices of $L_i$ and $L_j$ are adjacent. If $i-j=1$, any two vertices of $L_i$ and $L_j$ are connected via $v_{L_i} \to v_1 \to v_{L_j}\to v_{k+1}$ where $v_{L_i}$ and $v_{L_j}$ are any two vertices belonging to $L_i$ and $L_j$ respectively.

This proves, $diam(\bar{G})\le 3$

(3) Let $G$ be a regular graph with vertex degree $k$ and $diam(G)=3$. Using the same notation as in (2), let $v_1$ and $v_4$ be two vertices such that the shortest path between them has length $3$. Since, $G$ is regular with degree $k$, both $L_1$ and $L_2$ contain $k$ vertices each. There are $2k+2$ vertices and $k(k+1)$ edges. In, $\bar{G}$, a path from a vertex in $L_1$ to a vertex in $L_2$ on the lines of 4 of (2) has length $3$. Let $G'$ be the graph obtained by deleting the vertices $v_1$ and $v_4$ from $G$ (therefore, deleting all the edges incident on them too).

Note that $\bar{G'}$ is a regular graph with degree $2k-1-(k-1)=k$ and $2k$ vertices. Suppose $diam(\bar{G'})\ge 3$, then we cannot partition the vertices of $\bar{G'}$ in the form $\{v_1,L_1,\dots,L_m,v_{m+1}\}$ for some $m\ge 3$ as we would require at least $2+\mid L_1\mid +\mid L_{m} \mid=2k+2$ vertices while we have only $2k$ vertices. Hence, we prove that $diam(\bar{G'})=2$ and thereby $diam(\bar{G})=2$. ( $diam(\bar{G})=1$ would mean that $G$ had no edges at all contradicting the fact that $diam(G)=3$)

Related Question