Proof of Cyclic Graph Edges = Vertices Formula

  • Context: Undergrad 
  • Thread starter Thread starter Charles Stark
  • Start date Start date
  • Tags Tags
    Cyclic Graph Proof
Click For Summary

Discussion Overview

The discussion centers around the relationship between the number of edges and vertices in cyclic graphs, specifically whether the number of edges is equal to the number of vertices. Participants explore potential proofs and related concepts, including Euler's equation and properties of planar graphs.

Discussion Character

  • Exploratory, Technical explanation, Debate/contested

Main Points Raised

  • One participant questions the existence of a proof for the statement that in cyclic graphs, the number of edges equals the number of vertices.
  • Another participant references Euler's equation for planar graphs (v-e+f=2) as a potential proof for cyclic graphs, suggesting that cyclic graphs may be equivalent to planar graphs.
  • A different viewpoint suggests that the relationship seems obvious, describing a method of constructing cycles and proposing a mapping from edges to vertices that demonstrates a one-to-one correspondence.
  • Further elaboration includes the use of Kuratowski's theorem to argue that cycles are planar, although some participants express that this might be an overly complex approach for the original statement.
  • One participant expresses regret for asking the initial question, indicating a realization that they could have found the answer through further reading.

Areas of Agreement / Disagreement

Participants express differing views on the necessity and complexity of proofs related to the relationship between edges and vertices in cyclic graphs. There is no consensus on a definitive proof or agreement on the implications of Euler's equation for this specific case.

Contextual Notes

Some assumptions regarding the definitions of cyclic and planar graphs are not explicitly stated, and the discussion does not resolve the mathematical steps or implications of the proposed proofs.

Charles Stark
Messages
31
Reaction score
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
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 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 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!
 

Similar threads

Undergrad A way to comprehend the geometry of a hypercube
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad Circuits or edge-disjoint unions of circuits in a connected graph
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Edge connectivity of a graph given the number of edge disjoint paths
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Number of edges in a tree digraph
  • · Replies 5 ·
Replies
5
Views
2K
Python Help solving a geometrical matching issue with Graph Neural Networks
  • · Replies 1 ·
Replies
1
Views
3K
High School 4-colours theorem can be proved visually
  • · Replies 21 ·
Replies
21
Views
2K
Undergrad The number of intersection graphs of ##n## convex sets in the plane
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Finding if a subgraph of a minimal non-planar graph is maximal planar
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Question regarding degrees of a graph and its biconnected components
  • · Replies 34 ·
2
Replies
34
Views
6K
Graduate Concrete examples of randomness in math vs. probability theory
  • · Replies 11 ·
Replies
11
Views
3K