Let G and H be simple graphs. Show $k$(GvH)= min {$v$(G)+$k$(H),$v$(H)+$k$(G)}

396 Views Asked by At

where $k$ is connectivity and v is the join operation.

This problem's got me really confused, I can't find any relation between the connectivity and the amount of vertices

1

There are 1 best solutions below

2
On

Hint: What happens when you delete vertices from $G \vee H$? If you still have vertices from both $G$ and $H$ remaining, is it possible that it is disconnected?