Proof of Cyclic Graph Edges = Vertices Formula

[Charles Stark]

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.

 

[FactChecker]

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.

 

[homeomorphic]

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.

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.

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.

 

[Charles Stark]

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.

I can't believe I asked this question lol

I should have just kept reading. Thanks!

 

[blue_raver22]

Thank you for bringing this up. While there may not be a specific proof for the statement that the number of edges in a cyclic graph is equal to the number of vertices, it is a well-known property of cyclic graphs and can be easily demonstrated through a few examples.

First, let's define what a cyclic graph is. A cyclic graph is a graph where each vertex is connected to the next vertex in a circular manner, creating a loop. This means that if we start at any vertex and follow the edges, we will eventually end up back at the starting vertex.

Now, let's consider a simple example of a cyclic graph with 4 vertices. We can label the vertices as A, B, C, and D. Starting at vertex A, we can see that there are 3 edges connecting it to the other vertices (A-B, A-C, A-D). Similarly, vertex B has 3 edges (B-A, B-C, B-D), vertex C has 3 edges (C-A, C-B, C-D), and vertex D has 3 edges (D-A, D-B, D-C). This gives us a total of 12 edges for our 4-vertex cyclic graph.

Now, let's generalize this for any cyclic graph with n vertices. Since each vertex is connected to the next vertex, we can say that each vertex has n-1 edges. For example, in our 4-vertex graph, each vertex had 3 edges (4-1=3). Therefore, for an n-vertex cyclic graph, the total number of edges would be n(n-1).

On the other hand, we know that the number of edges in a graph can also be calculated using the formula E = V(V-1)/2, where E is the number of edges and V is the number of vertices. If we substitute n for both E and V in this formula, we get n(n-1)/2.

Equating these two formulas, we get n(n-1) = n(n-1)/2, which simplifies to n = n/2. This shows that the number of edges in a cyclic graph is equal to the number of vertices, as stated in the original statement.

In conclusion, while there may not be a specific proof for the statement, we can easily demonstrate it through examples and generalize it for any cyclic graph with n vertices. This property is important to understand when analyzing and studying cyclic graphs in various