# Basic Graph Theory Question

1. Oct 23, 2014

### 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 $$3v/2 \equiv 0 (mod 3)$$.

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.

#### Attached Files:

• ###### Gp17.JPG
File size:
15.2 KB
Views:
70
2. Oct 28, 2014

### 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.

3. Oct 31, 2014

### 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!)

#### Attached Files:

• ###### Photo on 10-31-14 at 5.50 PM.jpg
File size:
14.2 KB
Views:
59
4. Oct 31, 2014

### FactChecker

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

5. Nov 2, 2014

### 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.