# Proof of fundamental domain in a graph

I am reading "Groups, Graphs and Trees" by John Meier and can't quite understand the proof of Lemma 1.52. More specifically, let's focus on the hexagonal example he gives. He also says something like "If there are only finitely many orbits of vertices and the graph is locally finite, then in the sequence there will be a maximal subgraph satisfying the conditions above". Why is this true?

In the hexagonal example, those condition hold but I don't see why we should have a maximal subgraph. Suppose we start with one of the outer vertices and then go along one of the outer edges. Suppose that we go along $$1/4$$ in length, then another $$1/8$$ and so on. So we get a chain of subgraphs but there is no maximal one and I also don't see how to obtain the CORE from here.

Could someone please clarify this part about how CORE is constructed? Thanks a lot!

EDIT: Here's the excerpt from the book  • Could you please include a screenshot (or PDF link if the text is legally available online)? Aug 9, 2020 at 12:10
• What is the statement of the lemma, conditions, and sequence? Also what you are describing doesn't sound like a subgraph.
– user29123
Aug 9, 2020 at 22:20

Suppose that we go along 1/4 in length, then another 1/8 and so on. So we get a chain of subgraphs but there is no maximal one and I also don't see how to obtain the CORE from here.

What you are describing is not a subgraph it is just a union of edge segments. Graphs are made up of edges and vertices, you don't include partial edges. Note that fundamental domains are closed and the union of what you describe won't be closed, it would be something like $$[0,1)$$.

How do you construct a CORE in the hexagon, $$\Gamma$$, example? First just choose any vertex, say the center one, as a subgraph and call it $$C_0$$. It satisfies the properties outlined in the beginning of the proof if $$v$$ is the center vertex. $$C_1$$ will be some graph subgraph which contains $$C_0$$ (the vertex) properly, is connected, and satisfies condition (2). In this case extend by any edge (so a single "spoke"). This turns out to be CORE since there are only two orbits of vertices and $$C_1$$ contains both (it contains two vertices) so adding any more vertices will contradict (2) and there is no way to add more edges without adding vertices (between any two, not necessarily distinct, vertices there is at most one edge).

He also says something like "If there are only finitely many orbits of vertices and the graph is locally finite, then in the sequence there will be a maximal subgraph satisfying the conditions above".

The finite orbit of vertices puts an upperbound on the number of vertices you can have so any increasing chain, if you are adding vertices, will stop at some point. The local finite condition basically says that you can't have an infinite increasing chain where you are only adding edges between some finite collection of vertices. That gives that some $$C_n$$ will be a maximal subgraph satisfying (1) and (2).

• Thank you for your answer! Generally speaking, indeed we take subgraphs to consist of a subset of the vertices and a subset of the edges and if that's what was meant in the proof, then it is clear. However, the author previously introduced the idea of treating the whole graph as a space - not just as a set of vertices and edges. So, for example, consider the second example of a fundamental domain he gave - he considered that as a subgraph. Aug 11, 2020 at 7:20
• @thebogatron I don't have a copy of the book on me but I am pretty sure that the second domain wouldn't be considered a subgraph even in this book. Maybe Meier talks about a subdiving graphs to get a fundamental domain eventually in which case that would apply (I don't remember how exactly it is approached in the book). If you think about the graph as a space (as I generally do) that doesn't mean subspaces are subgraphs just like subsets of groups are not subgroups―there is more structure going on. For graphs it is a combinatorial structure/data and for groups is is something algebraic etc.
– user29123
Aug 11, 2020 at 8:05
• I don't think there is any harm in thinking about it as a subgraph though except for the fact it might confuse some ideas (like what you bring up in the question) or could make some definitions or theorems weird to state (like vertex transitive action)
– user29123
Aug 11, 2020 at 8:10
• Ok it makes sense now, thanks a lot! Aug 11, 2020 at 8:27