 # Prove that if diam(G)=3 for a regular graph G, then d i a m ( <mrow class="MJX-Te Mayra Berry 2022-06-10 Answered
Prove that if diam(G)=3 for a regular graph G, then $diam\left(\overline{G}\right)=2.$.
I know that without using regularity one can show that if . How do I use regularity to show that it must be exactly 2?
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it Punktatsp
Suppose G is a graph with diam(G)>2 and $\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}\left(\overline{\mathrm{G}}\right)>2;$; I will show that G is not regular.
More precisely, let $x,y,v,w$ be vertices with ${d}_{G}\left(x,y\right)>2$ and ${d}_{\overline{G}}\left(v,w\right)>2;$; I will show that $\mathrm{deg}\left(v\right)+\mathrm{deg}\left(w\right)>\mathrm{deg}\left(x\right)+\mathrm{deg}\left(y\right),$, the degrees being computed in G.
Clearly $x,y,v,w$ are four distinct vertices, $vw\in E\left(G\right),$ and $xy\in E\left(\overline{G}\right).$ Since ${d}_{\overline{G}}\left(v,w\right)>2,$ at least one of the edges $xv,xw$ is in E(G); without loss of generality, we assume that $xv\in E\left(G\right).$ It readily follows that , and $xw\in E\left(\overline{G}\right).$.
Let $S=V\left(G\right)\setminus \left\{x,y,v,w\right\}.$. Let m be the number of edges (of G) between S and $\left\{v,w\right\},$, and let n be the number of edges between S and {x,y}. Then $\mathrm{deg}\left(v\right)+\mathrm{deg}\left(w\right)=m+4,$, and $\mathrm{deg}\left(x\right)+\mathrm{deg}\left(y\right)=n+2.$
Since each vertex in S is joined (by an edge of G) to at least one vertex in $\left\{v,w\right\}$ and to at most one vertex in {x,y}, we have $m\ge n;$; it follows that
$\mathrm{deg}\left(v\right)+\mathrm{deg}\left(w\right)=m+4>n+2=\mathrm{deg}\left(v\right)+\mathrm{deg}\left(w\right).$