Minimal number of edges in a 4 connected graph

133 Views Asked by At

For $n\ge 5$, what is the minimal number of edges of a $4$-connected graph on $n$ vertices? (denote this number by $j(n)$).

All I could establish is $j(n) \ge 2n$ as for each connected graph $G$, $k(G)\le\delta(G)$.

Thus, if $G$ is $4$-connected we get $e(G) \ge \frac{n\delta(G)}{2}\ge \frac{nk(G)}{2} \ge 2n$.

Thanks.

1

There are 1 best solutions below

1
On BEST ANSWER

$2n$ is the correct value. Start from a cycle and then add an extra edge from each vertex to the vertex two spaces clockwise. Can you show that this is $4$-connected?