Difficulty in understanding the proof of “The centre of every connected graph $G$ is a subgraph of some block of $G$”

graph theorygraph-connectivity

I was going through the text A First Course in Graph Theory by Chartrand, Zhang. There I came across the above theorem and it's proof. But I had difficulty in understanding it in few places.

Theorem : The center of every connected graph $G$ is a subgraph of some block of $G$.

Proof:

  1. Assume, to the contrary, that $G$ is a connected graph whose center $Cen(G)$ is not a subgraph of a single block of $G$.
  2. Then there is a cut-vertex $v$ of $G$ such that $G-v$ contains two components $G_1$ and $G_2$, each of which contains vertices of $Cen(G)$.
  3. Let $u$ be a vertex of $G$ such that $d(u,v)=e(v)$ and let $P_1$ be a $u-v$ geodesic in $G$.
  4. At least one of $G_1$ and $G_2$ contains no vertices of $P_1$. Say $G_2$ contains no vertices of $P_1$.
  5. Let $w$ be a central vertex of $G$ that belongs to $G_2$ and let $P_2$ be a $v-w$ geodesic.
  6. Then $P_1$ followed by $P_2$ produces a $u-w$ geodesic, whose length is greater than that of $P_1$.
  7. Hence $e(w)>e(v)$, which contradicts the fact that $w$ is a central vertex of $G$.

Now in point $(3)$ the authors assume that $G-v$ has two components (exactly)? then again in point $(4)$ "At least one of $G_1$ and $G_2$ contains no vertices of $P_1$". If none of the components contain vertices of $P_1$ then where will the vertices go? I guess the authors meant $G-v$ contains at least two components of which $G_1$ and $G_2$ contains vertices of $Cen(G)$ in point $(3)$.

In the proof where are we using the fact, that vertices of $Cen(G)$ belongs to two separate blocks? While proving we assume $w \in V[Cen(G)]$ to belong to $G_2$, where I feel we are only considering a single vertex in a single component. Now suppose if $w$ is the single vertex present in $V[Cen(G)]$, then as per this proof we still arrive at a contradiction I guess. This is the part which I cannot understand…

Best Answer

I guess the authors meant $G−v$ contains at least two components of which $G_1$ and $G_2$ contains vertices of $Cen(G)$ in point (3).

Yes, that's what the authors mean.

In the proof where are we using the fact, that vertices of Cen(G) belongs to two separate blocks?

This is used in point (4). Specifically, the vertices of $P_1 - v$ are contained in a single connected component of $G-v$. This component can be $G_1$, $G_2$, or some other connected component of $G-v$. Since both $G_1$ and $G_2$ contains a central vertex, in all three cases we can find a central vertex not contained in the same component, which is what we need for the rest of the proof.

Related Question