- #1

- 31

- 5

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.

- Thread starter Charles Stark
- Start date

- #1

- 31

- 5

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

FactChecker

Science Advisor

Gold Member

- 6,049

- 2,336

- #3

- 1,768

- 126

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.

- #4

- 31

- 5

I can't believe I asked this question lol

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 should have just kept reading. Thanks!