Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Basic Graph Theory Question

  1. Oct 23, 2014 #1
    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!
     

    Attached Files:

  2. jcsd
  3. Oct 28, 2014 #2

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  4. Oct 31, 2014 #3
    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:

  5. Oct 31, 2014 #4

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    Ha! That's a good way of generating them.
     
  6. Nov 2, 2014 #5

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook