Possible Number of Vertices for Graphs with Three Edge Connections

[metapuff]

I want to create graphs where each vertex has three edges, and is connected by these three edges to three distinct vertices.

I'd like to know the number of vertices for which this is possible. By playing around a bit, I've found that it's possible for graphs with 4, 8, and 12 vertices. If v is the number of vertices, it's easy to see that a necessary (but not sufficient) condition is that [tex]3v/2 \equiv 0 (mod 3) [/tex].

The attached image shows exactly what I'm looking for. The graphs for the tetrahedron, cube, and dodecahedron all satisfy my criteria, while the others do not.

Thanks in advance!

 

[FactChecker]

Take any example and notice that any vertex can be expanded into a triangle where each vertex of the new triangle connects to one of the edges that came into the expanded point. Start with the simplest case (the tetrahedran) and expand the center vertex. That gives a new example with 6 vertices, 9 edges and 5 faces (counting the exterior as a face). You can continue expanding one vertex at a time, each time getting another example with 3 more edges, 2 more vertices, and one more face. I think you can continue this forever to exhaust all possibilities.

 

[metapuff]

Yeah, that's totally correct. It's pretty easy to see that any even number of vertices will work, while any odd number will not. For the case of an even number of vertices, the attached image shows a pattern that works every time. (duh!)

 

[FactChecker]

Ha! That's a good way of generating them.

 

[FactChecker]

There is another point to make that might already be obvious. There are a lot of other ways to generate graphs with those properties that are not equivalent to these graphs.