Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a paragraph from "Regular polytopes" by Coxeter that I don't understand.

Although it is not always possible to include all the vertices of a polyhedron in a single chain of edges, it certainly is possible to include then all as nodes of a tree (whose $N_0-1$ branches occur among the $N_1$ edges). This merely requires repeated application of the principle that any two vertices may be connected by a chain of edges. In fact, every connected graph has a tress for its "scaffolding" (Geruest), and the connectivity of the graph is defined as the number of its branches that have to be removed to produce a tere, namely $1-N_0+N_1$.

$N_0$ is a number of vertices, $N_1$ is a number of edges and $N_2$ is a number of faces of polyhedron. I don't know a lot about graph theory (I understand basic concepts but this seems to skip a lot of steps for a beginner). Could you explain to me this paragraph using a bit less math-oriented language and go with examples or something?

The paragraph is on 9th page, it goes right after the paragraph that says that not all graphs satisfy that Hamilton's problem about imagining vertices as cities we want to visit and edges the only roads between them. It's all still about three-dimensional polytopes (polyhedra).

I hope you can help me understand this and sorry that this isn't a strict question asking for a certain answer, but more like an open question.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

What he means is that the graph (of the polytope) might not always yield a Hamilton path (which is a single chain of edges), but can always yield a tree (no cycles). This is trivially true of any graph.

You then have to show that a connected tree has $N_0 - 1$ edges only, so from $N_1$ edges, you have to remove $N_1 - N_0 + 1$ edges.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.