How to prove this theorem?

Question

This is really bugging me, how do I prove this theorem?

The minimum number of vertices to connect n edges is n-1 (we're talking Euler and Hamiltonian circuits from discrete math).

Steve · Accepted Answer

If the vertices are numbered 1,2,3....n you don't have an edge until you get to #2, and you're done when the last edge hits #n.  Since #1 isn't in the count for edges, they will number one less than the vertices.

All this is true only if #1 and #n are non-coincident.

elve_r · Answer

Start with the fact that if you take one edge and want to connect it to all others, that would be n-1 edges

bulman · Answer

The assertion of the theorem became into got here upon on a Babylonian pill circa 1900-1600 B.C. whether Pythagoras (c.560-c.480 B.C.) or somebody else from his college became into the 1st to discover its info can't be claimed with any degree of credibility. Euclid's (c 3 hundred B.C.) factors supply the 1st and, later, the same old reference in Geometry.

Anonymous · Answer

a

Trending News

How to prove this theorem?

4 Answers