Feasible subgraphs containing at most $d-2$ nonsimple vertices

37 Views Asked by At

In a paper concerning the reconstruction of polytopes from their graphs I have the following lemma

Lemma 4.4:

Let $P$ be a $d$-polytope , and let $H$ be a feasible subgraph of $G(P)$ containing at most $d-2$ nonsimple vertices. If $G(F)$ of some facet $F$ is contained in $H$, then $H\cong G(F)$

The proof starts by stating that it is true if $H$ and $F$ have the same vertices. Then we suppose that the vertex of $F$ are strictly included in those of $H$. Then it says:

in which case any path from a vertex in $H\backslash G(F)$ to a vertex in $G(F)$ must pass through a non-simple vertex, since simple vertices have the same degree in both $H$ and $G(F)$

I don't get this. To start with there doesn't even necessarily exist any non simple vertices.

PS: A feasible sub-graph of $G(P)$ is a $(d-1)$-connected sub-graph of $G(P)$ whose simple vertices (i.e. simple in $P$) each have degree $d-1$ and each non-simple vertex has degree $\geqslant d-1$

1

There are 1 best solutions below

0
On BEST ANSWER

Since $F$ is a facet of $P$, any simple vertices of $P$ which are in $F$ have degree $d-1$ in $F$.

Suppose $v$ is a vertex in $H$ but not in $G(F)$, and consider a path from $v$ to some vertex in $G(F)$. Suppose $w$ is the first vertex of $G(F)$ along this path. If $w$ is simple in $P$, then it has degree $d-1$ in both $G(F)$ and in $H$; so all the edges incident to $w$ in $H$ are also in $G(F)$, and so all its neighbors are in $G(F)$. Thus $w$ could not be the first vertex on the path which is in $G(F)$, contradiction.

So, the first vertex of $G(F)$ along the path must be a non-simple vertex.

(As you say, there aren't necessarily any non-simple vertices, which is fine. That would just mean that $G(F)$ and $H$ must coincide, which is what we're trying to prove.)