- #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.

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- 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,964

- 2,893

- #3

- 1,772

- 127

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 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!

Share: