Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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:
