Why can the complete graph K5 be embedded on a torus?

2.2k Views Asked by At

In the Question Which complete graphs can be embedded on a torus? the poster says, that the complete graph $K_5$ can be embedded on a torus.

But the Euler characteristic of the torus is 0 and the Euler characteristic of $K_5$ is 2. Shouldn't they be the same if $K_5$ can be embedded on the torus?

1

There are 1 best solutions below

2
On BEST ANSWER

The Euler characteristic of $K_5$ is not $2$. A graph does not have an Euler characteristic.

A graph can have genus, which is the minimum genus of any orientable surface it can be embedded in; since $K_5$ can be embedded in a torus, which has genus $1$, we know that $K_5$ has genus at most $1$. (Since $K_5$ is not planar, we know it does not have genus $0$, therefore it has genus exactly $1$.)

For orientable surfaces, the genus $g$ and the Euler characteristic $\chi$ are related by $\chi = 2-2g$, so if you wanted to, you could define the Euler characteristic of a graph by this formula. This is not commonly done. By this definition, the Euler characteristic of $K_5$ would be $0$ - the same as that of the torus.

An equivalent way to phrase this definition would be that the Euler characteristic of a graph is the maximum Euler characteristic of any orientable surface it can be embedded into. So we'd conclude that whenever a graph is embedded in an orientable surface, its Euler characteristic must be less than or equal to that of the surface, and that's true here, so we're fine.