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.


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.

You can see this easily by drawing a random graph on a piece of paper. Here is the first example that I found on the web, in which you will see many examples of vertex pairs which are ends of edges, and other vertex pairs which are not; no graph isomorphism can take one kind of vertex pair to the other.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.