Show that if $G$ is $k$-connected and $H$ is $t$-connected then $G+H$ is $(k+t)$-connected

Question

The exercise is given as the title says, I've just watched in this question the case of $K_1$ so I do wonder, do I have to make a similar proof? Or there's a different way to make it?

Proof(Attempt): Since $G$ is $k$-connected so there is $k$ different disjoint paths between each vertices $u,v$ in $G$. In the same way for $H$ and $t$. So after we make the join between the graphs, each vertex in $G$ is now adjacent to each vertex in $H$, thus there exist at least $k+t$ disjoint paths for each vertex in $G+H \\ \therefore G+H \text{ is $(k+t)$-connected}$.

Honestly, I've got the sensation that this proof is a little bit void, it is alright? there are some details that I missed? Any suggestions/hints?

Answer 1

I would only give few additional details. Let $u,v \in V(G+H)$.

1. If $u\in V(G)$ and $v\in V(G)$, then by definition of $G$, there are $k$-disjoints paths from $u$ to $v$ in $G$. And by definition of +, $u$ and $v$ are connected to all vertices of $H$. $H$ is $t$-connected therefore $V(H)\geq t$, giving you at least $t$ additional disjoint paths from $u$ to $v$.
2. If $u\in V(H)$ and $v\in V(H)$, you have a symmetric argument
3. Now if If $u\in V(G)$ and $v\in V(H)$. $G$ is $k$-connected therefore $u$ has at least $k$ neighbour in $G$, calls them $w_1,\ldots,w_k$. Again by definition of +, there are edges between all $w_i$ to $v$. Then all $uw_iv$ are disjoint paths from $u$ to $v$. With a simmetric argument there are $t$ disjoint path $ux_iv$ with $x_i\in N_H(v)\subseteq H$. Therefore you have $k+t$ disjoint paths.

Answer 2

The main flaw in your proof is that you do not say what the $k+t$ paths are (which is the straightforward way to justify that there are $k+t$ paths).

There is also an alternative argument that does not invoke Menger's theorem, and gives a stronger result.

For any $S \subseteq V(G) \cup V(H)$, $G \vee H - S$ (I'm using $G \vee H$ to denote the join because $G+H-S$ looks silly) is definitely connected if $V(G) - S$ and $V(H)-S$ are both nonempty. In that case, for any $v,w \in V(G)$ there is a two-step $v,w$-path through an intermediate vertex in $V(H)$, for any $v,w \in V(H)$ there is a two-step $v,w$-path through an intermediate vertex in $V(G)$, and if $v\in V(G)$ and $w \in V(H)$ then $vw$ is an edge.

So if $G\vee H - S$ is disconnected, then either $V(G) \subseteq S$ or $V(H) \subseteq S$. In the first case, $G\vee H - S$ is a subgraph of $H$, and we need to delete at least $t$ more vertices from $V(H)$ to disconnect it. In the second case, $G \vee H - S$ is a subgraph of $G$, and we need to delete at least $k$ more vertices from $V(G)$ to disconnect it. So $$\kappa(G\vee H) \ge \min\{|V(G)| + t, |V(H)| + k\}$$ and in particular because any $n$-vertex graph is at most $(n-1)$-connected, $$\kappa(G \vee H) \ge k+t + 1$$ so $G \vee H$ is $(k+t+1)$-connected. (Assuming $K_1$ is $0$-connected, which is consistent with other definitions.)