1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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