Subgraph isomorphisms: does large out-expansion imply large in-expansion?

Question

Let $G$ be a directed graph, and $H$ a subgraph of $G$ that contains all the vertices of $G$. (In other words, $H$ is obtained by deleting some of the edges of $G$, but not any of the vertices of $G$.)

A subgraph isomorphism $\varphi$ from $G$ to $H$ is a graph isomorphism from some subgraph of $G$ to $H$. In other words, it is a bijective function $\varphi:V\to V$ (where $V$ is the vertex set of $G$) such that if $(\varphi(u),\varphi(v))$ is an edge in $H$, then $(u,v)$ is an edge in $G$.

Let $\Phi$ denote the set of all subgraph isomorphisms from $G$ to $H$. For a vertex $v \in V$, define the out-expansion of $u$ in $\Phi$ to be $|\{\varphi(v) : \varphi \in \Phi\}|$ (i.e., the number of vertices that $v$ can be mapped to, under some subgraph isomorphism), and the in-expansion of $v$ to be $|\{\varphi^{-1}(v) : \varphi \in \Phi\}|$ (i.e., the number of vertices that can map to $v$, under some subgraph isomorphism).

Consider the following proposition:

If every vertex has out-expansion $\ge k$, then every vertex has in-expansion $\ge k$.

Is this proposition true for all $G,H$?

I haven't been able to find any reason why it should be true. (For instance, I don't think $\Phi$ is closed under inversion: $\varphi \in \Phi$ doesn't seem to imply $\varphi^{-1} \in \Phi$.) However, playing with a few small examples, I haven't found a counter-example yet. That said, I only tried a few simple examples, so it's possible that more trial-and-error might give a better sense. But I thought I'd check whether anyone here has any suggestions for how to answer this.

Motivation: this problem arises in the security analysis of a proposed scheme for obfuscating/protecting circuits. The graph represents the circuit (actually, they use a colored graph, where each vertex is given a color, and the isomorphism has to respect the color scheme; but that can probably be ignored, for simplicity), and subgraph isomorphisms represent different possible ways that the circuit might have been hidden/obfuscated.

Answer 1

Yes: if each vertex maps to at least $k$ vertices by a set $S$ of bijections of a finite set, then there are at least $k$ vertices that map to each vertex by these bijections.

In fact, the in-spectrum (the sequence of in-expansions) is a permutation of the out-spectrum (the sequence of out-expansions). Note that $f$ is a bijection iff $f^{-1}$ is a bijection. Hence one can define a bijection between $S$ and $S^{-1} = \{f^{-1}\mid f\in S\}\ $ so the spectra are then permutations of each other.

---

An aside: this doesn't necessarily hold for bijections of infinite sets. Let $f_i$ be the map $1\mapsto i, 2\mapsto 1, 3\mapsto 2, \dots, i \mapsto i-1, i+1\mapsto i+1,\dots$, and take the collection of all these maps. Then the out-spectrum is $(\omega,2,2,\dots)$ while the in-spectrum is $(2,2,2,\dots)$.