Proof of Cyclic Graph Edges = Vertices Formula

In summary, the conversation discusses the relationship between the number of edges and vertices in cyclic graphs. It is noted that for cyclic graphs, the number of edges is equal to the number of vertices. A proof for this statement is sought, and the conversation explores various methods, including Euler's equation for planar graphs and Kuratowski's theorem. Ultimately, it is concluded that all cycles are planar and therefore have the same number of edges and vertices.
  • #1
Charles Stark
31
5
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.
 
Physics news on Phys.org
  • #2
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.
 
  • #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.

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.
 
  • #4
Charles Stark said:
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!
 
  • #5


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
 

1. What is the "Proof of Cyclic Graph Edges = Vertices Formula"?

The "Proof of Cyclic Graph Edges = Vertices Formula" is a mathematical formula used to determine the number of edges in a cyclic graph based on the number of vertices present.

2. How is the formula derived?

The formula is derived using the Euler's formula for planar graphs, which states that for a connected planar graph with V vertices, E edges, and F faces, the equation V - E + F = 2 holds true. By substituting F = 1 (since a cyclic graph has only one face), the formula is simplified to V - E + 1 = 2, which can be rearranged to E = V - 1. Hence, the "Proof of Cyclic Graph Edges = Vertices Formula" is E = V - 1.

3. What is the significance of this formula?

This formula is useful in various applications of graph theory, such as in computer science and network analysis. It allows for quick and efficient calculation of the number of edges in a cyclic graph, which can help in problem-solving and optimization tasks.

4. Can this formula be applied to all types of graphs?

No, this formula is specifically for cyclic graphs, which are a type of connected planar graph. It cannot be applied to other types of graphs such as directed graphs or multigraphs.

5. Is there a practical example of using this formula?

Yes, for instance, in a transportation network, the nodes (vertices) can represent cities, and the edges can represent roads connecting them. By using the "Proof of Cyclic Graph Edges = Vertices Formula," we can determine the minimum number of roads needed to connect all cities in a cyclic pattern.

Similar threads

Replies
1
Views
777
  • Engineering and Comp Sci Homework Help
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
464
  • General Math
Replies
21
Views
1K
Replies
2
Views
679
Replies
1
Views
1K
Replies
1
Views
921
  • Computing and Technology
Replies
2
Views
240
Replies
34
Views
3K
Back
Top