1
$\begingroup$

I'm trying to understand the answer to this question:

If $G$ is simple with diameter two and maximum degree $|V(G)| - 2$, then $|E(G)| \geq 2|V(G)| - 4$

The person that answered claimed that if $deg(v)=n-2$ then $G-v$ is connected, but I just don't understand that part (highlighted below):

"It is easy to see that $G−v$ is a connected graph. (There is a vertex $u$ of $G−v$ which is not adjacent to $v$; every other vertex of $G−v$ is connected to $u$ by a path in $G$ of length at most $2$; since there is no edge $uv$, that path must be contained in $G−v$.)..."

$\endgroup$
1
  • $\begingroup$ the diameter characteristic is on G. If I eliminate v on G, does the new graph G still have the same characteristic? that is what I trying to understand. How did he know that "every other vertex of G−v is connected to u by a path in G of length at most 2"? because the diam is the max distance. $\endgroup$ Commented Jan 17, 2019 at 13:25

1 Answer 1

3
$\begingroup$

Let $G$ with $diam(G)=2$ and max degree $\Delta(G)=n-2$. Then let $v$ a vertex such that $d(v)=n-2$.

There exist a unique $u$ such that $v$ and $u$ are not connected, $v \nsim u$.

Now, for all $w\in V(G-\{v\})$, we know that in $G$, the distance between $w$ and $u$ is at most 2. But as $u$ is not connected to $v$, the 2-edges-path from $w$ and $u$ cannot pass through $v$. Therefore the path from $u$ to $w$ exists also in $G-v$. This is true for any $w\neq v$, therefore $G-v$ is connected.

Edit Even more : you don't need $d(v)=n-2$, you only need $d(v)\leq n-2$ to get at least one vertice $u$ satisfying the condition. Therefore as long as the maximum degree $\Delta(G)$ is at most $n-2$ (which is the case here), then for any $v$ , $G-v$ is connected, and therefore $G$ is 2-connected.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .