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.

  • $\begingroup$ Select[GraphData[], (GraphData[#, "VertexConnectivity"] >= 3) &] $\endgroup$ Apr 21, 2013 at 1:58
  • $\begingroup$ 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 $\endgroup$
    – Szabolcs
    Apr 21, 2013 at 2:03
  • $\begingroup$ @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.) $\endgroup$ Apr 21, 2013 at 2:17
  • $\begingroup$ @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. $\endgroup$ Apr 21, 2013 at 2:19
  • $\begingroup$ @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? $\endgroup$ Apr 21, 2013 at 12:10

1 Answer 1


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.


     GraphUtilities`ToCombinatoricaGraph[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) &]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.