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. 



What is the chromatic number of the graph whose vertices dimension $n-2$ subsimplicies of $\Delta^n$ and an edge between two vertices is given if the two associated $n-2$ vertices are contained in the same $n-1$ subsimplex?   
It is known that the complete graph $K\_{2m}$ has a 1-factorization
(e.g., <http://en.wikipedia.org/wiki/Graph_factorization>). This means
that its set of edges can be written as a disjoint union of $2m-1$
complete matchings $M\_1, \dots, M\_{2m-1}$, each with $m$ edges. If $e$
is an edge of $K\_{2m}$ regarded as a 2-element subset $\lbrace
i,j\rbrace$ of $[2m] = \lbrace 1,2,\dots, 2m\rbrace$, then let
$\bar{e}$ denote the complement $[2m]-\lbrace i,j\rbrace$, and let
$\bar{M}\_i =\lbrace \bar{e}\colon e\in M\_i\rbrace$. Color the elements
of $\bar{M}\_i$ with the color $i$. This gives a proper coloring
of the $2m-3$ simplices of $\Delta^{2m-1}$ in $2m-1$ colors.


