Embedding of utility graph in two torus

Question

I'm trying to show that there exists an embedding of the utility graph in the two-torus such that its complement is connected. Trying to solve the question by drawing an actual $2$-torus and experimenting with different configurations is tedious and doesn't seem to be getting me anywhere. When I used gluing polygons I run into the issue of being unable to visualize how a line looks on the $2$-torus (e.g., when a line leaves one side, how does it look coming out of the corresponding inverse side?)... Is there an intuitive way of solving this problem? Could someone help me to answer this problem?

Answer 1

I don't think this is possible. Label the houses as A,B,C and utilities a, b, c. Then AbCaBcA is an embedded loop. Cut the torus along it. The result is diffeomorphic to a cylinder. Cut it along the arc connecting A to a; the result is diffeomorphic to a disc. Connecting B to b will disconnect the disc.

To say it in other words, $H_1$ of the graph is 4 dimensional, and $H_1$ of the torus is 2 dimensional. Any embedding of the graph will induce a map on $H_1$, mapping $\mathbb{Z}^4\to \mathbb{Z}^2$. This will have a kernel, and anything in that kernel represents a separating loop in the torus.

Update: Some more explanations that don't fit well into a comment.

I) Simply put, you can compute the Euler characteristic of the embedding's complement to be 3. Since the complement has no homology in degrees 2 or above, it must have $H_0\geq 3$, so at least 3 components.

This is similar to the (quite informal) argument in Theorem 5.1 Chromatic Graph Theory reference from Alex's answer.

To make this rigorous and prove the impossibility of the embedding for the (most general) case of Jordan embeddings, one can in fact compute homology of the complement using Mayer-Vietoris repeatedly. This is in the style of the proof of (part of) Jordan curve theorem in Hatcher's Algebraic Topology book, Proposition 2B.1.

First, one proves that complement of a Jordan arc in $T^2$ is connected (this is similar to Proposition 2B.1.(a)), and its inclusion to $T^2$ induces isomorphism on $H_1$. Then one computes homology groups of the complement in $T^2$ of larger and larger pieces of the graph, adding one edge at a time, using Mayer-Vietoris.

Namely, suppose $G=G_0\cup e$, and $P=G_0\cap e$ is either a single vertex or a pair of vertices (if both vertices of $e$ are in $G$). Then $T^2\setminus P= (A=T^2\setminus G_0) \cup (B=T^2\setminus e)$ and $A\cap B= T^2\setminus G$. In the case when $P$ is two points, writing down Mayer-Vietoris for reduced homology with field coefficients, we see that either we get non-zero reduced $H_0(A\cap B)$ (meaning the complement is disconnected) or we must have $H_1(T^2\setminus G)$ have rank 1 lower than $H_1(T^2\setminus G_0)$. (When $P$ is one point, the rank of $H_1$ is preserved). Building up $K_{3,3}$ edge by edge we will get 4 instances when new edge creates an extra loop, and $H_1$ starts at rank 2, so can not drop 4 times. Thus at the 3rd time at the latest we will get a bump in $H_0$ and will disconnect the complement.

II) In the (much nicer) category of $C^1$ embeddings things are easier (I think most of what I will say also holds in the category of locally flat embeddings, but I don't know that category too well). Below all the curves are assumed to be at least piecewise $C^1$.

After I cut a torus along a loop, I could not get a Mobius band because the result is orientable; also, if the loop is smooth, then because the torus is orientable if I orient the loop I know which way is "clockwise" from the direction of the loop, so I can (for a smooth loop) push my loop in both "clockwise" and "counterclockwise" directions, to get different parallel copies; this gives a neigborhood $N$ of the loop that looks like a standard cylinder, and after I cut I will have two boundary circles (not one as in the Mobius band). This argument is not applicable verbatim to piecewise smooth curves, but the corresponding neighborhood theorem is still true (there is a neighborhood $N$ of the loop $\gamma$ such that $(N, \gamma)$ is homeomorphic to $(\text{Cylinder, belt circle})$. There are two options: either these two circles are part of the boundary of a single component (such a loop is called non-separating), or of two different ones (such a loop is called separating). The second case is of no interest to us, since it means we have already disconnected the torus. The in the first case we have a surface with one component, two boundary circles, and Euler characteristic 0, so it must be homeomorphic to a cylinder by classification of compact surfaces with boundary.

The fact that separating loops are the ones for which the class they represent in H_1 is zero follows from applying Meyer-Vietoris. In the smooth (and piecewise smooth) case we can apply it to the decomposition of the torus into the "collar neighborhood" $N$ and the complement of the loop (and studying the connecting maps, some of which are induced by inclusion). (Note that the fact that a separating loop is null-homologous is intuitively clear -- it is the boundary of (either) piece it separates the surface into; if it is non-separating then one could think it intuitive that there is "no way" it can be a boundary of anything -- where would this cycle live? The Mayer-Vietoris argument is a way to make this rigorous.)

Alternatively, in the smooth case, any two non-separating loops are taken to each other by some diffeomorphism of the torus (this is a general statement of mapping class group acting transitively on the surface, but for the torus can be shown more directly), so we can after making this diffeomorphism assume that the loop is a "standard" one, and after we cut we get a cylinder.

I do not at the moment have a reference in mind for this.

Answer 2

When I was a boy I was given the three utilities problem. I almost solved it, it remains for me to draw only one remaining edge. Later I has told that this problem has no solution. But how could we know this? There are plenty of drawing possibilities and a solution can be so intricate that we have overlooked it. Probably, I had to try more hard.

Now the theory is again against us. By Theorem from [B, p. 6], if a graph $G$ has $V$ vertices, $E$ edges and $F$ faces and $G$ can be drawn on a torus then $V- E + F = 0$. Since we have $V=6$ and $E=9$, $F=3>1$. The exact conditions which have to satisfy the drawing are listed at the same page. In particular, any region in the torus whose boundary is given by a collection of paths corresponding to edges in $G$ is a face, that is it should look like a connected open subset of $\Bbb R^2$.

Now recall some facts on embedding graph on surfaces from [CZ].

While a torus is a sphere with a handle, a sphere with $k$ handles, $k\ge 0$, is called a surface of genus $k$ and is denoted by $S_k$. Thus, $S_0$ is a sphere and $S_1$ is a torus. The surfaces $S_k$ are the orientable surfaces.

Let $G$ be a nonplanar graph. When drawing $G$ on a sphere, some edges of $G$ will cross. The graph $G$ can always be drawn so that only two edges cross at any point of intersection. At each such point of intersection, a handle can be suitably placed on the sphere so that one of these two edges pass over the handle and the intersection of the two edges has been avoided. Consequently, every graph can be embedded on some orientable surface. The smallest nonnegative integer $k$ such that a graph $G$ can be embedded on $S_k$ is called the genus of $G$ and is denoted by $\gamma(G)$. Therefore, $\gamma(G) = 0$ if and only if $G$ is planar; while $\gamma(G) = 1$ if and only if $G$ is nonplanar but $G$ can be embedded on the torus. In particular, $$\gamma(K_5) = 1\mbox{ and }\gamma(K_{3,3}) = 1.$$

Suppose that $G$ is a graph embedded on a surface $S_k$, $k\ge 0$. A region of this embedding is a $2$-cell if every closed curve in that region can be continuously deformed in that region to a single point. (Topologically, a region is a $2$-cell if it is homeomorphic to a disk.) ... An embedding of a graph $G$ on some surface is a $2$-cell embedding if every region in the embedding is a $2$-cell.

Farther, at page 136 (not available in the Google book) is stated that the following result [Y] was proved by J. W. T. (Ted) Youngs (1910–1970).

Theorem 5.23 Every embedding of a connected graph $G$ of genus $k$ on $S_k$, where $k\ge 0$, is a 2-cell embedding. see

With the aid of Theorems 5.22 and 5.23, we have the following.

Corollary 5.24 If G is a connected graph of order n [that is with $n$ vertices. AR] and size $m$ [that is with $m$ edges. AR] that is embedded on a surface of genus $\gamma(G)$, resulting in $r$ regions, then $$n − m+ r = 2 − 2\gamma(G).$$

So for the graph $K_{3,3}$ embedded on a torus we have the equality $V- E + F = 0$ stated above.

References

[B] Padraic Bartlett, Toroidal Graphs, UCSB 2014.

[CZ] Gary Chartrand, Ping Zhang, Chromatic Graph Theory, p. 133-135.

[Y] J. W. T. Youngs, Minimal imbeddings and the genus of a graph, J. Math. Mech. 12 (1963), 303–315.

Answer 3

What is a 2-torus? The term seems to have two different meanings.

In one of them, a 2-torus is just our ordinary torus, called "2-torus" because it is a manifold of dimension 2. In this view an "$n$-torus" would mean the topological product of $n$ circles. (Compare the use of "2-sphere" for an ordinary sphere).

In the other meaning a 2-torus is still a two-dimensional surface, but in contrast to the ordinary torus it has two holes. In other words, this is homeomorphic to a sphere with two handles.

$K_{3,3}$ doesn't embed into the first sense of 2-torus with a single face (we can see this by computing the Euler characteristic, as Alex Ravsky does in his answer).

But $K_{3,3}$ does embed into the second sense of 2-torus with a single face. Namely:

• Take an ordinary sphere and draw $K_{3,2}$ -- that is, three houses and two utilities -- on it. This produces a graph with three faces.

• Put the third utility in one of the faces.

• Attach two handles between this face and the other two faces. This fuses the faces into one.

• Dig two of the supply lines from the third utility such that they go across the handles. The third supply line stays away from the handles. We now have one of the three supply lines ending in each of the original faces; connect them to the houses one by one.

• Convince yourself that the complement of the graph is still connected.