# Message #2252

From: Roice Nelson <roice3@gmail.com>

Subject: Re: [MC4D] color graph

Date: Tue, 05 Jun 2012 13:06:19 -0500

>

> Any graph can be embedded in R3 without crossings. I believe that this one

> can’t be embedded in R2 without crossings.

>

ah, I hadn’t considered making that general statement, but it makes perfect

sense. I think you’re right about this one not being a planar

graph<http://en.wikipedia.org/wiki/Planar_graph>,

since it lives on the projective plane.

For R3 embeddings of graphs, here’s something interesting that is

reminiscent of crossings. There are some graphs that must have linked

cycles when embedded. An example is the Peterson

graph<http://en.wikipedia.org/wiki/Petersen_graph>,

which is the graph of a hemi-dodecahedron. No matter how you embed it, at

least two of the pentagonal faces will be linked.

> How does one search for a graph? That sounds super-useful!

>

Wolfram Alpha has an ever increasing library of graphs. Ed Pegg, Jr. of

mathpuzzle.com told me he and others are constantly extending that

database. You can search for things like "graph on 11

vertices<http://www.wolframalpha.com/input/?i=graph+on+11+vertices>",

and that query currently has over 500 results, names and pictures, etc. I

can’t seem to search for graphs with a particular number of vertices and

edges though, which seems like a big limitation (maybe there is a way).

Googling things like "graph with 11 vertices and 20 edges" can be helpful

as well, when you’re initially trying to find your way around. In the

past, those kinds of searches have led me to collections like this

one<http://www.win.tue.nl/~aeb/graphs/index.html>

.

I wouldn’t be surprised if there are queryable databases of graphs out

there. If anyone knows of such a thing, please do share.

seeya,

Roice