Graph theory proving question on connected graphs

67 Views Asked by At

Let $G_1$ and $G_2$ be two vertex disjoint (that is $V(G_1)\cap V(G_2) = \emptyset$) connected graphs of order at least $2$. Let $H = G_1 + G_2$. Prove that $\text{Cen}(H)$ is always a connected graph.

1

There are 1 best solutions below

0
On BEST ANSWER

Case 1: For $i=1,2$ no vertex of $G_i$ is adjacent to every other vertex of $G_i$.

Case 2: For $i=1,2$, some vertex of $G_i$ is adjacent to every other vertex of $G_i$.

Case 3: For $i=1$ or $2$ no vertex of $G_i$ is adjacent to every other vertex of $G_i$, but for $j=1$ or $2$ some vertex of $G_j$ is adjacent to every other vertex of $G_j$.

In all cases note that the distance between two vertices is at most $2$, as you can get from one to the other by going to a vertex in the other graph, and (if necessary) back.