Return to Answer

This was confirmed by support to be a bug.

One workaround is to use Combinatorica`VertexConnectivity:

graph1 = CycleGraph[8];
graph2 = UndirectedGraph[
   Graph[{1 -> 3, 1 -> 7, 1 -> 10, 2 -> 5, 2 -> 6, 3 -> 6, 3 -> 10, 
     4 -> 7, 4 -> 8, 4 -> 9, 5 -> 9, 6 -> 10, 7 -> 8, 8 -> 9}]];

Block[{$ContextPath},
 Needs["Combinatorica`"];
 Needs["GraphUtilities`"]
 ]

Combinatorica`VertexConnectivity@
   GraphUtilities`ToCombinatoricaGraph[#] & /@ {graph1, graph2}

See here for the purpose of Block around Needs.

P.S. It turns out that the GraphUtilities`ToCombinatoricaGraph function re-adds Combinatorica to the context path every time it's called. If you prefer not to have Combinatorica in the context path, you can consider editing GraphUtilities.m and changing Needs["Combinatorica`"] to Block[{$ContextPath}, Needs["Combinatorica`"]].

This was confirmed by support to be a bug.

One workaround is to use Combinatorica`VertexConnectivity:

graph1 = CycleGraph[8];
graph2 = UndirectedGraph[
   Graph[{1 -> 3, 1 -> 7, 1 -> 10, 2 -> 5, 2 -> 6, 3 -> 6, 3 -> 10, 
     4 -> 7, 4 -> 8, 4 -> 9, 5 -> 9, 6 -> 10, 7 -> 8, 8 -> 9}]];

Block[{$ContextPath},
 Needs["Combinatorica`"];
 Needs["GraphUtilities`"]
 ]

Combinatorica`VertexConnectivity@
   GraphUtilities`ToCombinatoricaGraph[#] & /@ {graph1, graph2}

See here for the purpose of Block around Needs.

P.S. It turns out that the GraphUtilities`ToCombinatoricaGraph function re-adds Combinatorica to the context path every time it's called. If you prefer not to have Combinatorica in the context path, you can consider editing GraphUtilities.m and changing Needs["Combinatorica`"] to Block[{$ContextPath}, Needs["Combinatorica`"]].

This was confirmed by support to be a bug.

One workaround is to use Combinatorica`VertexConnectivity:

graph1 = CycleGraph[8];
graph2 = UndirectedGraph[
   Graph[{1 -> 3, 1 -> 7, 1 -> 10, 2 -> 5, 2 -> 6, 3 -> 6, 3 -> 10, 
     4 -> 7, 4 -> 8, 4 -> 9, 5 -> 9, 6 -> 10, 7 -> 8, 8 -> 9}]];

Block[{$ContextPath},
 Needs["Combinatorica`"];
 Needs["GraphUtilities`"]
 ]

Combinatorica`VertexConnectivity@
   GraphUtilities`ToCombinatoricaGraph[#] & /@ {graph1, graph2}

See here for the purpose of Block around Needs.

P.S. It turns out that the GraphUtilities`ToCombinatoricaGraph function re-adds Combinatorica to the context path every time it's called. If you prefer not to have Combinaotirca in the context path, you can consider editing GraphUtilities.m and changing Needs["Combinatorica`"] to Block[{$ContextPath}, Needs["Combinatorica`"]].

This was confirmed by support to be a bug.

One workaround is to use Combinatorica`VertexConnectivity:

graph1 = CycleGraph[8];
graph2 = UndirectedGraph[
   Graph[{1 -> 3, 1 -> 7, 1 -> 10, 2 -> 5, 2 -> 6, 3 -> 6, 3 -> 10, 
     4 -> 7, 4 -> 8, 4 -> 9, 5 -> 9, 6 -> 10, 7 -> 8, 8 -> 9}]];

Block[{$ContextPath},
 Needs["Combinatorica`"];
 Needs["GraphUtilities`"]
 ]

Combinatorica`VertexConnectivity@
   GraphUtilities`ToCombinatoricaGraph[#] & /@ {graph1, graph2}

See here for the purpose of Block around Needs.

P.S. It turns out that the GraphUtilities`ToCombinatoricaGraph function re-adds Combinatorica to the context path every time it's called. If you prefer not to have Combinatorica in the context path, you can consider editing GraphUtilities.m and changing Needs["Combinatorica`"] to Block[{$ContextPath}, Needs["Combinatorica`"]].

This was confirmed by support to be a bug.

One workaround is to use Combinatorica`VertexConnectivity:

graph1 = CycleGraph[8];
graph2 = UndirectedGraph[
   Graph[{1 -> 3, 1 -> 7, 1 -> 10, 2 -> 5, 2 -> 6, 3 -> 6, 3 -> 10, 
     4 -> 7, 4 -> 8, 4 -> 9, 5 -> 9, 6 -> 10, 7 -> 8, 8 -> 9}]];

Block[{$ContextPath},
 Needs["Combinatorica`"];
 Needs["GraphUtilities`"]
 ]

Combinatorica`VertexConnectivity@
   GraphUtilities`ToCombinatoricaGraph[#] & /@ {graph1, graph2}

See here for the purpose of Block around Needs.

P.S. It turns out that the GraphUtilities`ToCombinatoricaGraph function re-adds Combinatorica to the context path every time it's called. If you prefer not to have Combinaotirca in the context path, you can consider editing GraphUtilities.m and changing Needs["Combinatorica`"] to Block[{$ContextPath}, Needs["Combinatorica`"]].

This was confirmed by support to be a bug.

One workaround is to use Combinatorica`VertexConnectivity:

graph1 = CycleGraph[8];
graph2 = UndirectedGraph[
   Graph[{1 -> 3, 1 -> 7, 1 -> 10, 2 -> 5, 2 -> 6, 3 -> 6, 3 -> 10, 
     4 -> 7, 4 -> 8, 4 -> 9, 5 -> 9, 6 -> 10, 7 -> 8, 8 -> 9}]];

Block[{$ContextPath},
 Needs["Combinatorica`"];
 Needs["GraphUtilities`"]
 ]

Combinatorica`VertexConnectivity@
   GraphUtilities`ToCombinatoricaGraph[#] & /@ {graph1, graph2}

See here for the purpose of Block around Needs.

P.S. It turns out that the GraphUtilities`ToCombinatoricaGraph function re-adds Combinatorica to the context path every time it's called. If you prefer not to have Combinaotirca in the context path, you can consider editing GraphUtilities.m and changing Needs["Combinatorica`"] to Block[{$ContextPath}, Needs["Combinatorica`"]].