# How to get a list of 3-connected graphs?

I'd like to use GraphData to get a list of graphs with vertex connectivity at least 3. I know GraphData["Nonplanar", 6] gives all the nonplanar graphs on 6 vertices, but I can't figure out how to get GraphData to do a selection based on the "VertexConnectivity" property.

• Select[GraphData[], (GraphData[#, "VertexConnectivity"] >= 3) &] – J. M. is computer-less Apr 21 '13 at 1:58
• What J.M. said, with the caveat that that command will initiate a loooong download. It's good to be aware of this too: mathematica.stackexchange.com/q/22261/12 – Szabolcs Apr 21 '13 at 2:03
• @J.M: Thanks. If I'd also like to restrict by, say, "EdgeChromaticNumber" being 3, what's the best way? (I incorrectly assumed that it would be obvious to me how to generalize to more conditions.) – Kundor Apr 21 '13 at 2:17
• @Szabolcs: Thanks a lot for the pointer, that's good to know. I'm actually looking at 6-vertex graphs to start with (by putting GraphData[6] in the first part of J.M.'s command) so the download's not so bad. – Kundor Apr 21 '13 at 2:19
• @J.M.: I believe I answered my previous question (on adding more conditions), with the form e.g. Select[GraphData[{"Nonhamiltonian", "Nonplanar", "Connected"}, 7], (GraphData[#, "EdgeChromaticNumber"] == 3 && GraphData[#, "VertexConnectivity"] >= 3) &]. Is this correct? Would it be more efficient to somehow combine the two calls to GraphData in the condition, and is this even possible? – Kundor Apr 21 '13 at 12:10

It's been suggested that I combine the helpful information given in comments into an answer. To deal with the original question (restricting the list of graphs based on "VertexConnectivity"), use Select:

Select[GraphData[], (GraphData[#, "VertexConnectivity"] >= 3) &]


However, this particular property apparently has some bugs, detailed at "Is there something wrong with VertexConnectivity". To be safe, we can use the function from Combinatorica, like so.

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

Select[GraphData[],
(CombinatoricaVertexConnectivity[
GraphUtilitiesToCombinatoricaGraph[GraphData[#]]] >= 3) &]


This issue did not arise for me.

To combine multiple such conditions, use && between separate calls to GraphData, for instance:

Select[GraphData[], (GraphData[#, "EdgeChromaticNumber"] == 3 && GraphData[#, "VertexConnectivity"] >= 3) &]


All of these commands will take a very long time. It helps somewhat to preload all the information, getting all the downloads over with, which you can accomplish with GraphData[All, "Preload"]. But it still takes a long time to run. Restricting to graphs of a certain size makes it much quicker. To restrict to graphs on 7 vertices:

Select[GraphData[7], (GraphData[#, "EdgeChromaticNumber"] == 3 && GraphData[#, "VertexConnectivity"] >= 3) &]


You can also restrict this way based on the boolean properties, which GraphData can already do itself, as with "Nonplanar" in the question. Multiple ones may be combined like this:

Select[GraphData[{"Nonhamiltonian", "Nonplanar", "Connected"}, 7], (GraphData[#, "ChromaticNumber"] == 3) &]