Proof that ratio of vertices to edges in an infinite (square) grid is 1:2?

Question

I'm making the statement that the ratio of vertices to edges in an infinite square grid is $1:2$. I need this fact for deducing further theorems specific for my problem, however I can't find any theory on infinite grids.

I would prefer to cite some literature on that (maybe also for hexagonal and triangular grids).

If no formal literature exists that covers that issue I would want to write the proof. My thinking so far is each vertex has $4$ edges connected to it and each edge $2$ vertexes, which makes for a $2$ to $4$ ratio $-> 1:2$. However I feel this is not formal enough and the proof should involve infinity of the grid.

Please post possible literature or a formal proof if you think mine isn't sufficient.

Answer 1

If we're being "careful with $\infty$", then let's consider an $n \times n$ square grid (with $n^2$ vertices). In this grid, there are $(n-2)^2$ interior vertices, which have $4$ edges out of them; $4(n-2)$ edge vertices, which have $3$ edges out of them; $4$ corner vertices, which have $2$ edges out of them.

By the degree sum formula, adding these numbers gives twice the number of edges (because each edge is counted twice, once by each of its endpoints). If we call the number of edges $m$, then $$ 2m = 4(n-2)^2 + 3(4n-8) + 2(4) = 4n^2-4n $$ so there are $2n^2-2n$ edges. The ratio $\frac mn$ of edges over vertices is $\frac{2n^2-2n}{n^2} = 2 - \frac 2n$, which approaches $2$ as $n \to \infty$.

We can be fully rigorous and still do less work with asymptotic analysis. If we were to claim that each vertex has degree $4$, and therefore that $2m = 4n^2$, we would be wrong only for edges around the border. But there are $O(n)$ edges along each border, whose degree differs from $4$ by a constant, so we have $2m = 4n^2 + O(n)$, and therefore $\frac mn = \frac{2n^2 + O(n)}{n^2} = 2 + O(\frac1n)$. Once again, as $n \to \infty$, this approaches $0$.

Also, we can consider a finite toroidal square grid, which "wraps around" at the borders, Pac-Man style. Then every single vertex has degree $4$, and the ratio of vertices to edges is $1:2$ with no approximation.

Answer 2

Consider that any vertex has four edges connected to it. Pick two edges that are adjacent, that is, are adjacent sides of a square. The vertex and the two edges can be translated to every other vertex and this partitions all vertices and edges. Thus the ratio of vertices to edges is $1:2$. What is important is the local connection between vertices and edges despite the fact that there are many different ways of pairing edges and vertices. There is only one way that is translation invariant.

A similar proof applies to an infinite one dimensional grid where the ratio is $1:1$.

A similar proof applies to an infinite (triangular) grid where the ratio is $1:3$.

In general, if you have an infinite homogeneous grid with the degree of each vertex being a constant $D$, then since each edge connects exactly two vertices, the ratio of vertices to edges is $2:D$. This applies to infinite homogeneous trees as a special case.

So in the case of an infinite hexagonal grid the ratio is $2:3$.

The same proofs apply to a finite cycle, infinite cylinder, finite torus by formally identifying edges of infinite grids. It is clear that for a finite cycle there is a $1:1$ ratio of vertices to edges, and this also applies in the limit of an infinite cycle. The infinite total number of vertices or edges makes no difference. It is the local connections between them that counts.

If you want to be really careful, consider the lattice of points in the plane with integer coordinates as vertices with horizontal edges $\{(n,y)\}$ where $m\le y<m+1$, and vertical edges $\{(x,m)\}$ where $n\le x<n+1$. Each period square is $\{(x,y)\}$ where $n\le x<n+1, m\le y<m+1$ and each contains one lattice point $(n,m)$, one horizontal edge, and one vertical edge. The ratio is $1:2$ in any period square. Similar proofs apply to other cases.

Read the Wikipedia article Fundamental pair of periods for the related idea of fundamental period parallelogram which is very important in elliptic function theory.

Answer 3

The answer’s actually quite simple. Sure there’s a mathematical proof, given an $n \times n$ square, there will be $(n+1)²$ vertices and $2n(n+1)$ edges, which equals $∞²$ to $2∞²$ as $n$ goes to $∞$. However, this is the less fun explanation.

Let’s play a game, we construct a square grid completely out of vertices conjoined with edges. In the first image, we repeatedly add a line connected to a dot, in the second we add two lines connected to one dot, and on the far right we add $3$ connected to one. As you can see, if there aren’t enough vertices, there will end up being some missing lines, where as if there are too many, you end up with missing dots. Now, granted, depending on how you play the game, there might be some missing lines or dots either way, but unless there’s a $2$ to $1$ ratio, there’s no way you can fill in all the spaces. Go ahead, try it out, it’s impossible, no matter how hard you try.

I know that that explanation wasn’t as mathematical as one would hope, but I figured this would be a pretty one method problem, so I wanted to provide something unique from all the other answers. If, however, you want me to expand on my introductory explanation, just comment and if be glad to.