Suppose G is a graph with diam(G)>2 and $\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(\overline{\mathrm{G}})>2;$; I will show that G is not regular.

More precisely, let $x,y,v,w$ be vertices with ${d}_{G}(x,y)>2$ and ${d}_{\overline{G}}(v,w)>2;$; I will show that $\mathrm{deg}(v)+\mathrm{deg}(w)>\mathrm{deg}(x)+\mathrm{deg}(y),$, the degrees being computed in G.

Clearly $x,y,v,w$ are four distinct vertices, $vw\in E(G),$ and $xy\in E(\overline{G}).$ Since ${d}_{\overline{G}}(v,w)>2,$ at least one of the edges $xv,xw$ is in E(G); without loss of generality, we assume that $xv\in E(G).$ It readily follows that $yv\in E(\overline{G}),\text{}yw\in E(G),$, and $xw\in E(\overline{G}).$.

Let $S=V(G)\setminus \{x,y,v,w\}.$. Let m be the number of edges (of G) between S and $\{v,w\},$, and let n be the number of edges between S and {x,y}. Then $\mathrm{deg}(v)+\mathrm{deg}(w)=m+4,$, and $\mathrm{deg}(x)+\mathrm{deg}(y)=n+2.$

Since each vertex in S is joined (by an edge of G) to at least one vertex in $\{v,w\}$ and to at most one vertex in {x,y}, we have $m\ge n;$; it follows that

$\mathrm{deg}(v)+\mathrm{deg}(w)=m+4>n+2=\mathrm{deg}(v)+\mathrm{deg}(w).$

###### Not exactly what you’re looking for?

Ask My Question