1
$\begingroup$

Given $n$ vertices of a concave polyhedron (3D), what are the maximum amount of edges it can have?

I know for convex polyhedra the upper bound is $3n-6$. Does this also hold for concave polyhedra?

Also, if $3n-6$ edges is also the upper bound for concave polyhedra, is this due to the fact that every concave polyhedron can be represented as a planar graph?

$\endgroup$

1 Answer 1

1
$\begingroup$

It depends on how you define polyhedron. Do you allow "holes" like in a donut? While I have no answer to the case of general $n$ (this might be very hard), here is a polyhedron on $n=7$ vertices with the maximal number of

$${7\choose 2}=21 \;\text{ edges},$$

which is bigger than $3n-6=15$.

It is called the Császár polyhedron, and there is an edge between any two vertices:

$\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.