Take some arbitrary connected graph $G$. Define a set $S = \{E_1,E_2,E_3…E_n\}$ which is all the permutations of any amount of edges (including $0$ edges), as in any connected or disconnected sub-graph of $G$. Define a binary operation on the elements of $S$ as follows:
The binary operation will be "painting" edges. For any $E_i, E_j \in S$, define $E_i\cdot E_j$ as the following- if two of the edges in either $E_i$ or $E_j$ overlap, then don't paint the edge. If an edge in $E_i$ or $E_j$ do not overlap, then paint the edge. The resulting sub-graph generated (which is all the edges that wind up painted) is the element in $S$ that corresponds to this sub-graph.
I want to prove this is a group, but I seem to have to resort to waving my hands a lot and proving it using intuition. Let $H$ be the group described above. Here is my try:
-Binary Operation. Clearly, for any $E_i,E_j \in H$, it is clear that $E_i \cdot E_j$ is a member of $H$ since $E_i \cdot E_j$ results in a sub-graph of $G$, hence it is in $S$.
-Identity. The identity element $E_{id} \in H$ is the element that contains no edges (the trivial graph with no edges or vertices), which obviously will paint nothing, hence for any $E_i \in H$ we have that $E_{id}\cdot E_i = E_i \cdot E_{id} = E_i$
-Inverses. The inverse of any element $E_i \in H$ is just $E_i$, since $E_i^2$ will double-paint every edge, hence it will result in the trivial sub-graph, hence $E_i^2 = E_{id}$
-Associativity. This just intuitively seems like it will be associative; I am not sure how to prove this.
In case this is still confusing, I will offer a simple example. Let $G$ be a connected graph with $2$ edges and $3$ vertices denoted $A,B$ and $C$, where $B$ is the "center" vertex. Then, let $H$ be the group generated by $G$. Note that $G = \{e, AB, BC, ABC\}$, where $e$ is the identity. An example of using the binary operation is $ABC\cdot AB = BC$, since this double paints over $AB$, hence the only painted edge is $BC$.
Assuming this is indeed a group, I have some thoughts about it. Let $H$ be a group generated by some connected graph $G$ under the painting binary operation described. Then,
-The group is Abelian (the order in which we paint/double-paint does not matter)
-The group is not cyclic (unless it is generate by a graph with only $1$ edge), since for any element $E_i \in H$ we have that $E_i^2 = e$, the identity.
-The group must have even order, since the order of each element must divide the order of the group. Since the only possible order of each element is $2$, the group must have even order.
-Every element of $H$ can be formed into a group as well with the same binary operation, since all the elements are sub-graphs themselves, hence the graph that generates a subgroup of $H$ is seen as "gluing together" all the edges of each element. This is assuming that this works for disconnected graphs, of course.
-(This one I am not so sure of) Any combination of elements that includes the identity are subgroups of $H$
Anyways here are my final questions:
-Is this even a group?
-If it is, does it need to be generated by a connected graph? I do not think it does but I am not sure
-If this is a group, is there a way to rigorously prove it is a group? I assume I do not know enough about graph theory to prove this rigorously.
-If this is a group, is there any way to calculate the order of the group given the amount of edges/vertices? I want to say it is $n!$ where $n$ is the number of edges, but I think it is more complicated, and (intuitively) possibly
$$_nP_n + _nP_{n-1}+…+_nP_{1}$$
but I am not sure.
Please let me know if you have any questions?
Best Answer
For any set $X$, if you take the set of subsets of $X$ together with the binary operation of symmetric difference, you get a group. This is well-known and an easy exercise: Does the Symmetric difference operator define a group on the powerset of a set?
You are just taking $X$ to be the set of edges of a graph, but this makes no difference. At no point do you use connectedness or that there is even a graph! So this has nothing at all to do with graph theory.
If $X$ is finite, then the size of the resulting group is $2^{|X|}$ (since this is the number of subsets) and it is an elementary abelian 2-group. (Sometimes called a Boolean group.)