I'm new to graph theory, I'm finding it hard to get upon proofs.
To prove: An n-hypercube is n-vertex connected. Approaches I thought:
It holds true for
n=2, so assume it holds true for
n=k-1, and prove it for
n=k, so its proved by induction.
Prove that there are
nvertex disjoint paths between every pair of points (u,v) in the n-hypercube, then it's n-vertex connected. (right?)
Can someone please point me in the right direction? What different approaches are possible for this problem?
I'm unable to get think of solutions myself clearly. But after I know a solution, it seems easy. I want to improve my problem solving skills in graphs. Which types of problems would you recommend me to start with? Any resources would be highly appreciated. Thanks!