For context, I'm reading Graphs and Homomorphisms by Hell and Nesetril. I have some questions / confusions about a passage concerning the reconstruction conjecture (page 16-17 for anyone with the book). The book presents the conjecture:
Conjecture 1.28 Graphs $G$ and $H$ are isomorphic if and only if all their edge-removed subgraphs are isomorphic, i.e., if and only if there exists a bijection $\beta: E(G)\rightarrow E(H)$ such that $G-e \simeq H-\beta(e)$ for all $e\in E(G)$.
and then the passage after that I'm struggling to understand:
Since we are only making statements about isomorphic graphs, we may assume that both $G$ and $H$ have the same vertex set $V$. All graphs in this proof will have vertex set $V$, and we describe them by just giving their edge sets. If the desired bijection $\beta: E(G)\rightarrow E(H)$ exists, we may extend it to associate subsets of $E(G)$ with subsets of $E(H)$ so that for any nonempty set of edges $A$ we have $G-A \simeq H - \beta(A)$. Equivalently, for any proper subset $A\subset E(G)$ we have the graph formed by $A$ isomorphic to the graph formed by $\beta(A)$. This is possible, as can easily be seen by counting. Assume that $A$ consists of $k < |E(G)| = |E(H)| = m$ edges, let $N(G)$ denote the number of copies[1] of $A$ in $G$, and $N_e(G)$ the number of copies of $A$ in $G-e$. Then counting in two ways[2] we obtain $$(m-k)N(G) = \sum_{e}N_e(G) = \sum_e N_e(H) = (m-k)N(H),$$ and hence the number of copies of any particular $A$ is the same in $G$ and $H$ [3].
Here are my questions:
[1] It's not clear to me what 'number of copies' means here. Does it mean the number of subgraphs of $G$ that are isomorphic to $A$? Or is $N(G)$ just an 'indicator' function that says $A$ appears as a subgraph of $G$, with exactly the same labels on the edges (So $N(G)$ would always be $0$ or $1$)? Normally I'd assume the former isomorphic subgraphs interpretation, but that makes no sense for the counting argument that follows.
[2] What is being counted on the left hand side to obtain $(m-k)N(G)$? My first assumption was that for each edge $e\notin A$ (of which there are $m-k$), we track the (one singular??) appearance of $A$ in $G-e$, but this only makes sense if we assume $N(G)$ is the 'indicator that $G$ contains $A$'. But if that is what the notation means, then it's easy to get $N(G)\neq N(H)$ in general. My guess for this is that the notation hasn't been fully explained, and that $N(H)$ actually means the number of copies of $\beta(A)$ in $H$, but I'm not sure?
[3] In the book, the argument ends here. Why is the fact that the number of copies of $A$ (whatever that means in this context) is the same in $G$ and $H$ enough to conclude that $A\simeq \beta(A)$?
Short Version: What's going on in the counting argument here, and why does it suffice to show $A\simeq \beta(A)$?
I agree that this is written in a confusing way. At first sight, I thought that the authors are extending $\beta$ to subsets simply by defining $\beta(A) = \{\beta(e) : e \in A\}$ for each $A \subseteq E(G)$, and then showing that this satisfies $G - A \simeq H - \beta(A)$. But indeed, this is not what they seem to prove.
At second sight, I think that what they want show is that for each $A$, the number of copies of $A$ (more on that in a minute) in $G$ and in $H$ are equal. Then we can define $\beta$ simply by choosing a one-to-one mapping between these subgraphs in $G$ and $H$, and then doing this for each (isomorphism class of) $A \subsetneq E(G)$. This ensures that $A \simeq \beta(A)$. But in this case I can't see how $A \simeq \beta(A)$ implies $G - A \simeq H - \beta(A)$. On the other hand, later on they only seem to use the fact that the subgraphs of $G$ and $H$ are in one-to-one correspondence.
Under this second interpretation, the answers to your questions (1) and (2) are as follows:
(1): Your first interpretation is correct - $N(G)$ is the number of subsets $A' \subseteq E(G)$ such that the $A'$ and $A$ induce isomorphic subgraphs. Analogously, $N(H)$ is the number of subsets $A' \subseteq E(H)$ such that $A'$ and $A$ induce isomorphic subgraphs in $H$ and $G$, respectively. Note that $\beta$ does not appear in this definition.
(2): We count the set $X(G) = \{(e,A'): e \notin A' \subseteq E(G), A' \text{ and } A \text{ induce isomorphic subgraphs}\}$. For each $A'$, we have $m-k$ edges not in $A'$, so $|X(G)| = (m-k)N(G)$. On the other hand, for each edge $e$, we have $N_e(A)$ choices of $A'$ that do not contain $e$, so $|X(G)| = \sum_e N_e(G)$. We may define $X(H)$ analogously, and since $G - e \simeq H-e$ implies $N_e(G) = N_e(H)$, we have $|X(G)| = |X(H)|$ and consequently $N(G) = N(H)$, as desired.