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

Cyclic Graph Proof?

  1. Jan 3, 2015 #1
    I noticed that for cyclic graphs the number of edges is equal to the number of verticies. Is there a proof out there for this statement? Just curious...

    I was able to find the proof of the formula for finding the number of edges for complete graphs, I couldn't find anything related to the above.
     
  2. jcsd
  3. Jan 3, 2015 #2

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    Euler's equation for a planar graph is v-e+f = 2, where f=number of faces counts the exterior as a face. So that proves it for a planar graph. I assume any cyclic graph is equivalent to a planar graph.
     
  4. Jan 3, 2015 #3
    Seems kind of obvious. I just picture the graph being built up by edges that only have one vertex on them, and when you put it all together you get a cycle. So, you've built any cycle in a way that makes it clear that there are the same number of edges as vertices.

    As far as formal proofs go, you can define a mapping from edges by putting an orientation on the cycle, and then mapping each edge to the vertex that comes last, according to the orientation, and you can show that that map is onto and has an inverse, so that it's one to one. So the vertices and edges are in 1-1 correspondence, which means there are the same number of vertices and edges.

    A cycle is always of the form x1, e1, x2, e2..., e_n-1, x_n, e_n, x1, if you do a walk on it. From that expression of it, you can see how to define the mapping and its inverse.

    Seems like too big a hammer to use for this fact. I think the standard terminology is to call graphs that are actually embedded in the plane, plane graphs. Planar means equivalent to a plane graph. The existence of, say, regular polygons, proves that all cycles are planar. Cycles also have no K5 minors or K3,3 minors, so Kuratowski's theorem would do the trick, too, although it's too heavy of a hammer, again.
     
  5. Jan 6, 2015 #4
    I can't believe I asked this question lol

    I should have just kept reading. Thanks!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Cyclic Graph Proof?
  1. Reeb graph (Replies: 1)

  2. Graph on the iPad (Replies: 4)

  3. Geometrical Proofs (Replies: 3)

  4. Graph theory (Replies: 2)

  5. Proof by Induction (Replies: 4)

Loading...