Graph G with n vertices, with connectivity

[MathematicalPhysicist]

I have a graph G with n vertices, with connectivity $$\kappa(G)=k$$ i.e its k- connected, I need to show that
$$k(diam(G)-1)+2 \le n$$

where diam (G) is defined as the maximal number of edges between two vertices in G (the maximum of them all), in other words its diameter.

Any hints?
even references for a proof will be terrific.

 

[MathematicalPhysicist]

I thought even of showing it by induction on k (I forgot to say that k is bigger or equals 1).
For k=1, we need to show that $$diam G +1 \le n$$, which is obvious because if G is 1-connected then if we take out one vertex then it must be disconnected, which means that to pass from one vertex to another you need to cross thruogh at most n-1 vertices which means that $$diam G \le n-1$$.

Now for the inductive proof, assume it's correct for k-1 and prove for k.
If we look at graph G with connectivty k, then if we remove from it a vertex and its edges we still get a graph G', but this time with connectivy k-1, and $$diam(G') \le diam(G)$$, and from the inductive hypothesis:
$$(k-1)(diam(G')-1) +2 \le n-1$$
I don't see how from this to show that it's correct for k.
Anyone?

 

[ych22]

I only had some brief exposure to graphs in my CS algorithms class. Excuse me if I get in the way...

Is it possible to come up with an upper bound for diam(G) given n and k? After all, it is obvious from the given equation that diam(G) <= 1+(n-2)/k.

Please do reply with the answer if you manage to find it (I'm interested in knowing)

 

[MathematicalPhysicist]

Well thank you for enlightening me.

We know from Menger's theorem that a graph G is k-connected (vertex wise) iff for every two vertices in G they have k vertex-disjoint paths.

so between any two vertices in a graph, G we have another n-2 vertices from which to choose that will make k vertex-disjoint paths, so these paths in total will include at most (n-2)/k vertices, and because the maximal length between any two vertices is at most the number of vertices between them plus one, we get the conclusion.

Thanks, it's amazing how a subtelty can change the way you see something.

 

[ych22]

Well thank you for enlightening me.

We know from Menger's theorem that a graph G is k-connected (vertex wise) iff for every two vertices in G they have k vertex-disjoint paths.

so between any two vertices in a graph, G we have another n-2 vertices from which to choose that will make k vertex-disjoint paths, so these paths in total will include at most (n-2)/k vertices, and because the maximal length between any two vertices is at most the number of vertices between them plus one, we get the conclusion.

Thanks, it's amazing how a subtelty can change the way you see something.

Yay great!