# Minimum 6-connected graph on 200 vertices

Find the samllest number of edges in 6-vertex-connected graph on 200 vertices.

I think that the answer is 600 , using the fact that $\delta(G) \geq \kappa(G)$.

But the smallest 6-vertex-connected graph that I could come up with is $K_{6,194}$ (the complete bipartite graph with size 6 and 194) , which sounds like far from optimal...

A hint/intuition will be very helpful .

• I would think that the graph with adjacencies defined as $v_i$ is adjacent to $v_{j}$ with $j=((-1+i+n)\text{mod} 200)+1$, $n\in\{-3,-2,-1,1,2,3\}$. (I.e. $v_4$ is adjacent to each of $v_1,v_2,v_3,v_5,v_6,v_7$ whereas $v_1$ is adjacent to $v_{198},v_{199},v_{200},v_2,v_3,v_4$). Each vertex has exactly 6 edges, and you can check that it is in fact six-connected. – JMoravitz Jul 14 '15 at 17:25
• As Rebecca has deleted her answer, based on your comment there I've edited in the info about vertex connectivity, please roll back the edit if this is against your intention. – dtldarek Jul 14 '15 at 17:40
• @JMoravitz I thoguht about something almost identical (to connect each vertex to the next 6 vertices) , but it failed .Your example is excellent!! – UserB95 Jul 14 '15 at 18:25
• Here's another example: Let $G_i$ be a graph isomorphic to $K_5$ with $V(G_i) = \{v_i^1, v_i^2, v_i^3, v_i^4, v_i^5\}$, for $i = 1,2,\dots,40$. Now let $G$ be the union of all the $G_i$'s together with all edges $v_i^j v_{i+1}^j$ for $i=1,2,\dots,40$, and $j=1,2,\dots,5$, where subscripts are taken mod 40. There are 400 vertices, and you can check that it is 6-connected and 6-regular. – Perry Elliott-Iverson Jul 14 '15 at 20:01
• Note that JMoravit'z example is in fact, the answer, since in any $k$-vertex connected graph, all vertices must have degree at least $k$. – Irvan Jul 15 '15 at 9:50

I would think that the graph with adjacencies defined as $v_i$ is adjacent to $v_j$ with $j=((−1+i+n) \ mod \ 200)+1,$ $n∈\{−3,−2,−1,1,2,3\}$. (I.e. $v_4$ is adjacent to each of $v_1,v_2,v_3,v_5,v_6,v_7$ whereas $v_1$ is adjacent to $v_{198},v_{199},v_{200},v_2,v_3,v_4$). Each vertex has exactly 6 edges, and you can check that it is in fact six-connected(the easiest way is to see that thee are 6 vertex disjoint paths between every two vertices, then by Menger's we could conclude that the graph is 6 connected)