1
$\begingroup$

Prove that if $G $ is a connected graph, with at least three vertices, then it’s square graph $G^2$ is 2-connected.

My attempt: Let $G=(V,E)$. For a graph to be 2-connected, I understand that for every vertex $x \in V(G)$, $G-x$ is connected.

Now, I can see why the above statement is true through different examples for vertices greater than 3. However, I'm not sure how to prove it for the general case. My guess is that since the power is 2, we connect every $x_{i}$ vertice to $x_{i+2}$ and by doing this we're essentially putting all the vertices on cycles in the graph.

$\endgroup$
0
$\begingroup$

I'm assuming that $G^2$ is the Cartesian product of $G$ with itself.

Hint:

  • For any path $P = (v_1,v_2,\ldots,v_n)$ in $G$ and vertex $u \in V$ let $\langle P,u\rangle$ be the path in $G^2$ defined as $$\langle P,u\rangle = \Big(\langle v_1,u\rangle,\langle v_2,u\rangle,\ldots,\langle v_n,u\rangle\Big).$$
  • If $u$ and $v$ are connected in $G$, then there exists a simple path $P$ that connects them.
  • Thus, in the $G^2$ path $\langle P,u\rangle$ connects $\langle u,u\rangle$ with $\langle v,u\rangle$, and similarly \begin{align} \langle u,v\rangle \xrightarrow{\langle P,v\rangle} \langle v,v\rangle,\\ \langle u,u\rangle \xrightarrow{\langle u,P\rangle} \langle u,v\rangle,\\ \langle v,u\rangle \xrightarrow{\langle v,P\rangle} \langle v,v\rangle. \end{align}

I hope this helps $\ddot\smile$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.