Number of squares in a planar Graph

51 Views Asked by At

I need help with the following Graph Theory problem:

Let $G$ be a connected and planar Graph. Each area in the planar version of the Graph (including the outer area) is either a square or a hexagon. Also, There are exactly $3$ areas adjacent to each node (probably just means that the degree of each node is $3$). Determine the number of squares of $G$.

I created an equation with two variables: $4x + 6y = 2 * E$ where $x$ represents the number of squares and $y$ is the number of hexagons. Also, the number of areas: $x + y$. I plugged those values into the Eulers formula but I ended up with an equation consisting of two variables which has infinitely many solutions.

1

There are 1 best solutions below

0
On

Let there be $x$ squares, $y$ hexagons, $v$ vertices and $e$ edges in the graph. Then the following equalities hold:

$$v-e+x+y=2,$$

$$3v=2e,$$

$$4x+6y=2e.$$

Putting $v$ and $e$ from two last equalities into the first yields:

$$4/3x+2y-2x-3y+x+y=2.$$

From here we find

$$x=6.$$