# Cannot understand the notation |G → H|F?

I have copied a section from Bondy's Graph theory book:

The idea is to count the mappings between two simple graphs $$G$$ and $$H$$ on the same vertex set $$V$$ according to the intersection of the image of $$G$$ with $$H$$. Each such mapping is determined by a permutation $$\sigma$$ of $$V$$, which one extends to $$G=(V,E)$$ by setting $$\sigma(G):=(V,\sigma(E))$$, where $$\sigma(E):=\{\sigma(u)\sigma(v):uv\in E\}$$. For each spanning subgraph $$F$$ of $$G$$, we consider the permutations of $$G$$ which map the edges of $$F$$ onto edges of $$H$$ and the remaining edges of $$G$$ onto edges of $$\bar H$$. We denote their number by $$|G\to H|_F$$, that is: $$|G\to H|_F:=|\{\sigma\in S_n:\sigma(G)\cap H=\sigma(F)\}|$$

I personally deciphered the notation |G->H|F as no. of distinct mapping of edges from a spanning subgraph F of G to H and the remaining edges (edges of G - edges of F) being mapped to H' taken together. In short it would be most helpful if someone could explain what |G → H|F notation means, would be most helpful with a simple example graph. And sorry if it is a trivial question because I am new to graph theory and the biggest problem that I mostly face is understanding what a theorem means because of the extensive use of mathematical symbols and notations and I mostly interpret wrong or miss out something.

Subscript $$F$$.
$$G$$ and $$H$$ are two graphs on the same vertex set.
$$F$$ s a subgraph of $$G$$.
This notation is defined in the link.
$$|\;G\rightarrow H\;|_F$$ is the number of permutaitons of $$G$$ that map the edges of $$F$$ onto edges of $$H$$, and the rest of the edges of $$G$$ onto $$\overline{H}$$. I guess $$\overline{H}$$ is the complement of $$H$$ (on the same vertex set).

• I saw it but had trouble to understand 'the number of permutaitons of G that map the edges of F onto edges of H. For ex if we have a graph with 4 vertices a,b,c,d and edge set G is {(a,b),(b,c),(c,d),(d,a)} and F a subgraph of G with edge set {(a,b)} and H with {(a,b),(b,c),(c,a),(b,d)}. How would the mapping look like? Commented Jun 9, 2023 at 16:57

Suppose we have $$4$$ vertices; $$G$$ is a cycle (left) and $$H$$ is a path (right):

1--2    1--2
|  |       |
|  |       |
4--3    4--3


Imagine the vertices $$1, 2, 3, 4$$ as being in fixed locations. We first swap the vertices of $$G$$ around according to some permutation, and then we lay the result on top of $$H$$ and see how many edges match up. If $$\sigma$$ is the permutation $$(2\;3)$$ that swaps vertices $$2$$ and $$3$$ (but keeps $$1$$ and $$4$$ fixed), then the edges $$\{12, 23, 34, 14\}$$ of $$G$$ become $$\{13, 32, 43, 14\}$$ when we apply $$\sigma$$. Equivalently, the edges of $$\sigma(G)$$ are $$\{13, 23, 34, 14\}$$ (because order of endpoints doesn't matter). In a picture, here is how $$\sigma(G)$$ (left) compares to $$H$$ (middle):

1  2    1--2    1  2
|\/|       |       |
|/\|       |       |
4  3    4--3    4  3


Only one of the edges matches up: the edge $$23$$. So the graph $$F$$ consisting of their intersection is the graph above on the right: the graph with one edge $$23$$ and two isolated vertices.

In our example, the cycle graph $$G$$ has many automorphisms. For example, the permutation $$(1\;2)\;(3\;4)$$ which swaps vertices $$1$$ and $$2$$ and also swaps vertices $$3$$ and $$4$$ leaves $$G$$ unchanged (we take the square and reflect it horizontally, and we get back an identical square). So in fact, there are only three possible values of $$\sigma(G)$$, each one obtained by $$8$$ of the $$24$$ permutations of the vertex set:

1  2    1--2    1--2
|\/|     \/     |  |
|/\|     /\     |  |
4  3    4--3    4--3


Their intersections with $$H$$ are:

1  2    1--2    1--2
|               |
|               |
4  3    4--3    4--3


Call these graphs $$F_1$$, $$F_2$$, and $$F_3$$ from left to right. ($$F_1$$ is a graph with a single edge $$23$$; $$F_2$$ is a graph with two edges $$12$$ and $$34$$; $$F_3$$ is $$H$$ itself.)

Because each of these results corresponds to $$8$$ permutations, we get $$|G \to H|_{F_1} = |G \to H|_{F_2} = |G \to H|_{F_3} = 8.$$ For every other possible graph $$F$$, we have $$|G \to H|_F = 0$$.

• Crystal clear thank you very much.. Commented Jun 9, 2023 at 18:23
• This really helped. So as far as I understood there are surely 24 permutations of C4 out of which distinct are only 3 .Each 3 has eight instances each which when intersected with example H gives us still 3 distinct graphs one H itself of f1,f2,f3 Obviously and trivially we get eight instances of f1,f2 and f3 because it is derived from 3 distinct permutation of C4 but |G->H|F=8 bcoz each f1, f2,f3 is repeated eight times Also if we intersect it with f4 doesn't belong to f1,f2,f3 then |G->H|F4=0 bcoz no intersection yields F4. Hence, the last result. Commented Jun 9, 2023 at 18:33