Let us first remark that all of this takes place on the boundary of $\Delta^n$. The question that I wanted to solve that led to the question in the title is as follows: Let $f:\Delta^{n-1}\hookrightarrow\Delta^n$ be an injective map. What I would have liked to do is to extend that map to a map, $\tilde{f}:\partial\Delta^n\hookrightarrow\Delta^n$ such that the restriction of $\tilde{f}$ on any the n-1 simplices of the boundary is the original map $f$ up to an action of the symmetric group on n letters.

One can see with a little thought that the condition needed to be able to obtain this is as follows: First we construct the graph mentioned in the question. To recapitulate, the vertices of this graph are the set of n-2 simplicies. We then attach an edge between two vertices if the two n-2 simplices are contained in the same n-1 simplex. Let us call this graph $X_n$ for lack of better notation. One may extend build the $\tilde{f}$ if (and only if I believe) if the graph constructed is $n$ colorable.

Now by working it out by hand, I showed that this is impossible for $n=2$, possible for $n=3$ impossible for $n=4$ and I believe that it is impossible for dimensions above. What is a proof for this fact? I did the work by hand for the cases I mentioned. It would be even better to know the actual chromatic number for these graph.