If $G$ is a $(n,m)$ graph such that $\Delta(G)=n-2$ and any two non-adjacent vertices have a common neighbour, then $m\geq 2n-4.$

Question

Let $G$ be a graph of order $n$ and size $m$ such that $\Delta(G)=n-2$ and any two non-adjacent vertices have a common neighbour. Show that $m\geq 2n-4.$

Kindly advise on my proof. Thank you.

Let $v\in G$ such that $v$ is adjacent to$ v_1,..., v_{n-2}$ and not adjacent to $u.$

Then $\sum_{g\in G} \text{deg}(g) \geq (n-2)+(n-2) = 2n-4.$

Now suppose $u$ is adjacent to $v_1,...,v_k$ and not adjacent to $v_{k+1},..., v_{n-2}.$ Then $\sum_{g\in G} \text{deg}(g)$ will increase by at least $k+k=2k.$

Given $v_i(i=k+1,..., n-2), $ by assumption in the problem, there exists $v_j(j = 1,..., k)$ such that $v_j$ is adjacent to $v_i.$ We can assume $v_1$ will be adjacent to all $v_i(i=k+1,...,n-2).$

Then $\sum_{g\in G} \text{deg}(g)$ will increase by at least $n-2-k + n-2-k = 2n-4-2k.$

Hence, $2m = \sum_{g\in G} \text{deg}(g)\geq 2n-4-2k+2k+2n -4 = 4n -8.$

Answer 1

Let's take a constructive approach. We're given the following:

(1) $G$ has $n$ vertices

(2) $G$ has $m$ edges

(3) $\Delta(G)=n-2$, i.e. the maximum degree of any vertex in $V(G)=n-2$

(4) Any two non-adjacent vertices share a neighbor. That is, if $u,v\in V(G)$ such that $u\nleftrightarrow v$, then there exists some $w\in V(G)$ such that $u\leftrightarrow w$ and $v\leftrightarrow w$.

Let $v\in V(G)$ such that $\delta(v)=n-2$. Name the adjacent vertices $v_i$ such that $i\in\{1,\dots,n-2\}$. At this point, we know $|E(G)|\geq n-2$. In addition, our choice of $v$ implies that there must exist $u\in V(G)$ such that $v\nleftrightarrow u$. However, property (4) implies that $u\leftrightarrow v_j$ for some $j\in\{1,\dots,n-2\}$. Hence, $|E(G)|\geq n-1$.

We still need to consider whether or not $u$ is adjacent to any of the other vertices $v_\ell$, where $v_\ell\in\{1,\dots,j-1,j+1,\dots,n-2\}$. Notice that there are $n-3$ elements in this set. We don't know for sure how many of these vertices are adjacent to $u$, so let's assume that $u$ is adjacent to $k$ of these vertices where $0\leq k\leq n-3$. Thus, $|E(G)|\geq n-1+k$.

There remains $(n-3-k)$ vertices in the set $\{1,\dots,j-1,j+1,\dots,n-2\}$ which are not adjacent to $u$. Once again, property $(4)$ implies that each of these vertices must then be adjacent to some vertex which is adjacent to $u$. So it must be the case that $$|E(G)|\geq (n-1+k)+(n-3-k)=2n-4$$ or equivalently $m\geq 2n-4$.

Answer 2

Let $V(G)=\{v_1,v_2,...,v_n\}$ and suppose $v_1$ is the vertex with maximum degree, i.e. $\deg(v_1)=n-2$. W.L.O.G. let $v_1$ be adjacent to $\{v_2,...,v_{n-1}\}$, but not $v_n$. This implies $v_1$ contributes exactly $n-2$ edges to $e(G)$.

Now, $v_n$ must be adjacent to at least one of the vertices $v_2,...,v_{n-1}$. Again, W.LO.G. let $v_n$ be adjacent to the $k$ vertices in the set $V'=\{v_2,..., v_{k+1}\}$, and not adjacent to the $n-2-k$ vertices in the set $V''=\{v_{k+2},..., v_{n-1}\}$. This implies that $v_n$ contributes exactly $k$ edges to $e(G)$, that are distinct from those contributed by $v_1$. This also implies that, in order for every vertex in $V''$ to have a common neighbour with $v_n$, it must be adjacent to at least one vertex in $V'$. Equivalently, each of the $n-2-k$ vertices in $V''$ contribute at least one edge to $e(G)$, that are distinct from those contributed by $v_1$ and $v_n$.

Hence, in conclusion, $m \geq n-2 + k + n-2-k = 2n-4$.