# Every Vertex Bijection Induces a Graph Isomorphism/Symmetry

First some setup:

Definition 1.9 A graph $$\Gamma$$ consists of a set $$V(\Gamma)$$ of vertices and a set $$E(\Gamma)$$ of edges, each edge being associated to an unordered pair of vertices by a function "Ends": $$\text{ENDS}(e) = \{v,w\}$$ where $$v,w \in V$$. In this case we call $$v$$ and $$w$$ the ends of the edge $$e$$ and we also say $$v$$ and $$w$$ are adjacent.

We also allow the possibility that there are multiple edges with the same associated pair of vertices. Thus for two distinct edges $$e$$ and $$e'$$ it can be the case that $$\text{ENDS}(e) = \text{ENDS}(e')$$. We also allow loops, that is, edges whose associated vertices are the same.

Definition 1.14 A symmetry of a graph $$\Gamma$$ is a bijection $$\alpha$$ taking vertices to vertices and edges to edges such that if $$Ends(e) = \{v,w\}$$, then $$Ends(\alpha(e)) = \{\alpha (v),\alpha(v)\}$$. The symmetry group of $$\Gamma$$ is the collection of all its symmetries. We note this group by $$Sym(\Gamma)$$

I take it that a symmetry is a map from $$V(\Gamma) \cup E(\Gamma) \to V(\Gamma) \cup E(\Gamma)$$.

Let $$\overline{f} : V \to V$$ be some bijection. In any natural way, does $$\overline{f}$$ induce a symmetry on $$\Gamma$$? I.e., does there exists a symmetry $$f$$ such that $$f \bigg|_{V} = \overline{f}$$? Here's what I thought. If $$v \in V$$, simply define $$f(v) = \overline{f}(v)$$. Now for the edges. Let $$e \in E$$. Then $$\text{ENDS}(e) =\{v,w\}$$ for some $$v,w \in V$$. Define $$f(e)$$ such that $$\text{ENDS}(f(e)) = \{f(v),f(w)\}$$.

But this doesn't seem rigorous, particularly that last sentence; and I'm worried about the possibility of multiple edges (which of the multiple edges, if there are any, is it being sent to?). I think it's clear that it preserves adjacency, but how do I verify that it's bijective?

Injectivity: Let $$x,y \in V \cup E$$ be such that $$f(x) =f(y)$$. Obviously $$x$$ and $$y$$ can't belong to different sets. If $$x,y \in V$$, injectivity of $$\overline{f}$$ implies $$x=y$$. If $$x,y \in E$$, then $$Ends(x) = \{v_x,w_x\}$$ and $$Ends(y) = \{v_y,w_y\}$$, so $$Ends(f(x)) = Ends(f(y))$$ or $$\{f(v_x),f(w_x)\} = \{f(v_y),f(w_y)\}$$...?

Surjectivity: Let $$x \in E$$ (if $$x \in V$$, there's nothing to prove). Then there are $$v,w \in V$$ such that $$Ends(x) = \{v,w\}$$. By surjectivity of $$\overline{f}$$, there are $$v',w' \in V$$ such that $$f(v') = \overline{f}(v') = v$$ and $$f(w') = \overline{f}(w') =w$$...But the problem is that $$v'$$ and $$w'$$ might not be adjacent, right...?

The reason for my interest is that nearly every example in my book defines a map just on the vertices or just on the edges and simply asserts that it is a graph symmetry. My thought was that the author was presupposing this result I'm asking about.

EDIT

Ah, I think I came up with a counterexample: a square with a line segment connecting the bottom right vertex to a vertex not on the square (so the graph has five vertices). Define $$f$$ to permute the bottom left vertex and the vertex not on the square, fixing everything else. This defines a bijection on the vertices. But if the follow the above procedure, you get something that maps an edge to a non-edge.

I think the above procedure works for complete graphs. Any other graphs?

The situation that $$\overline f$$ induces a symmetry on $$\Gamma$$ is by far the exception rather than the general pattern.
The trouble with your proof scheme is this: assuming your definition $$f(v) = \overline f(v)$$, and given $$e \in E$$ such that $$\text{ENDS}(e) = \{v,w\}$$, there is no expectation in general that there even exists an edge whose ends are $$\{f(v),f(w)\}$$.
It's easy to see in fact that every example can be obtained from some complete graph $$G$$ on $$p$$ vertices by the following alteration: choose one constant $$q$$ and replace every edge of $$G$$ between a distinct pair vertices by $$q$$ edges between those same vertices; choose another constant $$r$$ and insert $$r$$ loop edges at each vertex. The parameters $$p,q,r$$ completely determine such graphs up to isomorphism.