I think the answer to Question 1 is yes, at least for finite graphs. Lets $(T,E)$ be a graph. You can choose a group $G$ that is large enough to do the following: For each node $x∈V$ choose a subgroup $G_x$ (called stabilizer) such that the intersection of all subgroups is $\{1\}$ and each subgroup has a different cardinality. Then you can form the graph in the following way: $$ V= \dot\bigcup_{t∈T} \{gG_t\mid g∈G\}, \mbox{ and } F=\{(gG_s,hG_t)\mid g,h∈G, (s,t)∈E\}.$$ Then each node $t$ is broken up into $|G/G_t|$ pairwise unconnected nodes. And each edge is split up into a complete bipartite graph connecting all equivalent vertices. By changing the group size and the size of the stabilizer you can ensure that any two edges in $F$ have the same valency iff they belong to the same node in $T$. For more information: - Monika Zickwolff: Darstellung Symmetrischer Strukturen durch Transversale, In: _Contributions to General Algebra_ 7, Teubner, Wien/Stuttgart - Daniel Borchmann and Berhard Ganter: Concept Lattice Orbifolds – First Steps, In: _Formal Concept Analysis_, LNAI 5548, Springer, p. 22