3
$\begingroup$

Let $G=(V,E)$ be a connected planar graph. This graph has an Euler characteristic given by $\chi=v-e+f$, where $v$ is the number of vertices, $e$ the number of edges and $f$ the number of faces.

I know that $\chi$ is a non-negative integer, but I was wondering which values $\chi$ can assume. Is it possible to determine some bounds on $\chi$?

2 Answers 2

1

Generally speaking, $\chi$ isn't bounded, and it can be negative or positive. For example, $\chi$ for a double torus is $-2$.

For planar graphs, $\chi$ is always 2. See this page for several proofs of this fact.

$\chi$ for a compact surface is given by the formula:

$\chi = 2(1 - g)$

Where $g$ is the genus of the surface, or more intuitively, the number of holes in it. This shows that $\chi$ can be decreased as much as we want by increasing the number of holes in a compact surface.

On the other hand, $\chi$ for $n$ disconnected spheres is $2n$. So similarly, we can increase $\chi$ as much as we want by increasing the number of spheres.

See Wikipedia's article for many more examples.

  • 0
    Of course we mustn't forget our non orientable friends- connected sum of projective planes which have $\chi$ = $2-n $, where n is the number of projective planes. :)2012-06-01
0

"The Euler characteristic of any planar connected graph $G$ is 2."