I've not been able to solve this problem for a week now. My idea was that I start with a circle with n nodes and because the edge connectivity is 3, every node must have at least 3 neighbours, so to have the biggest value of g(G) possible, i have to connect each node with the furthest distance, so the circle has a maximum length of n / 2 + 1. I can't seem to prove it for general graphs and I have no idea where to start and how to prove this formally.
1 Answer
$\begingroup$
$\endgroup$
Assume $g(G) \geq n/2 +2 $ that is, the shortest cycle C in G contains al least $n/2 +2 $ nodes. Consider x and y to be adjacent nodes in C$=(...w,x,y,z,...)$ if you were able to remove the edges $wx$ and $xy$ without disconecting x, then x must be adjacent to at least one of the $n/2 -2$ nodes outside C (it has to be outside C since we assumed it is shortest cycle). Similarly if $xy$ and $yz$ is not a cutset, then y is adjacent to a node outside C.
But this implies that the edge $xy$ is contained in a cycle that has at most $n/2$ vertices, wich is a contradiction. Thus either {wx, xy} or {xy, yz} is a cutset, then $ λ(G) =2 <3$.
So $ λ(G) =3 \rightarrow g(G) \leq n/2 +1$ ■
