Number of facets of a polyhedron when a vertex is removed My question, informally: I have a bounded polyhedron in R^n with k facets, and I want to remove a vertex of this problem. How many facets does the remaining polyhedron have at most?
More formally: Let P be a polyhedron in R^n. Then P = conv (vert P), where "vert P" gives the vertices of P and "conv" gives the convex hull of a set of points. I'm wondering whether there is an upper bound on the number of facets of conv (vert P \ { v }), where v is a vertex of P.
A simple upper bound is the following one: Using the Upper Bound Theorem, we can determine the maximum number of vertices for any polyhedron with k facets. Let this number be V. Then we can use the Upper Bound Theorem again to determine the maximum number of facets for any polyhedron with V - 1 vertices. This bound, however, seems very conservative.
Does anybody have an idea about a tighter bound? Any help would be much appreciated!

Thanks to everybody for the examples of "bad cases" where the removal of a vertex introduces many new facets. They confirm my suspicion that the number of facets can indeed grow significantly. I was wondering whether one can derive a non-trivial upper bound on the number of facets thereby introduced?
 A: Here is an explicit example where the number of facets can increase dramatically when removing a vertex from the convex hull.  Let $G$ be a graph and define the subgraph polytope $P(G)$ of $G$ to be the convex hull of all subgraphs of $G$.  That is, we take the convex hull of all vectors of the form $(\chi (F), \chi (S)) \in \{0,1\}^{E(G)} \times \{0,1\}^{V(G)}$, where $F$ and $S$ are the edges and vertices of a subgraph of $G$.  It is easy to check that the following system completely describes $P(G)$.
$$
0 \le z_v \le 1, \text{ for all $v \in V(G)$} \\
0 \le y_{vw} \leq z_v, \text{ for all $vw \in E(G)$}.
$$ 
Thus, $P(G)$ has $O(V(G)+E(G))$ facets. 
Define the non-empty subgraph polytope, $P^*(G)$ of $G$ to be the convex hull of non-empty subgraphs.  Thus, $P^*(G)$ is obtained by taking the convex hull of all vertices in $P(G)$, except for $(\mathbb{0}^{E(G)}, \mathbb{0}^{V(G)})$. Conforti, Kaibel, Walter, and Weltge show that $P^*(G)$ is the set of all $(y,z)$ satisfying the above inequalities together with the following additional constraints. 
$$
y(F) \leq z(V(G))-1, \text{ for all spanning forests $F$ of $G$}.
$$
Thus, $P^*(G)$ can have dramatically more facets than $P(G)$.  
A: When removing vertex $v$ by slicing by an $n-1$ dimensional plane $S$ in such a way that no other vertex is sliced off, every facet that includes $v$ transforms to a facet with an additional boundary component, but that is still just one facet.  And the intersection of the plane $S$ with the original polyhedron is the boundary of one additional facet, lying in $S$.  Therefore, the upper bound is  $k+1$ facets.
This upper bound is always saturated unless $S$ slices through some vertiex or vertices other than $v$.  For example, in a cube, if you slice off a little triangle near to one corner you are left with $6+1=7$ facets, one of which is a triangle, three pentagons, and three squares.  But if the slice passes through the three vertices connected by an edge to that corner, the facets go down to $4$, three triangles and a quadrilateral. 
However, in the last paragraph of the problem it becomes clear that this is not what the OP means, because he speaks of a polyhedron with $V-1$ vertices, and teh polyhedra formed by plane slicing have, in may cases, more than $V$ vertices.  (For example, the cube with a corner nipped has ten vertices.)
If you are restricted to lopping of a vertex such that no new vertices are created, then the most remaining facets are achieved when the slicing loses every facet attached to $v$ and gains the single new facet.  Now in $n$ dimensions each vertex intersects with at least $n$ facets. So the upper bound, achieved when slicing off a vertex that is in with just $n$ facets in such a way that the slicer goes through edges only at other vertices, is $k-n+1$.
Obviously, for a generic polyhedron, it may or may not be possible to slice off a specific vertex without creating new vertices, so this upper bound is not always achievable.
