Having a bit of trouble with this question:

Suppose G is a 4-regular connected graph with a planar embedding such that every face has degree 3 or 4, and further that any 2 adjacent faces have different degrees.

For the first part, I have to prove that G has no bridges and hence that every edge in G is on the boundary of 2 distinct faces.

For the second part, I must determine precisely the number of vertices, edges, faces of degree 3, and faces of degree 4 in G.

Something tells me to use Euler's formula for the second part but I'm quite confused at the first part.

Any help would be greatly appreciated!


To see that there's no bridges, assume that there is a bridge (say $uv$). Then as the graph is 4-regular, $u$ has four incident edges, and hence is itself incident to 3 faces (say $A$, $B$ and $C$), one of which is the "outer face" which is on both sides of the edge $uv$, but then we have a contradiction as all these faces are pairwise adjacent. So $A$ must have a different degree to $B$, without loss of generality assume these degrees are 3 and 4 respectively, but then $C$ is adjacent to $A$, so must have degree 4, but also adjacent to $B$ so must have degree 3.

The only wrinkle here is that the embedding does not actually need $uv$ to be on the outer face, but in this case we can see that it still is incident on only one face (otherwise it's not a bridge).

A.Schulz's answer already covers the rest of the question well.


For the first part of the answer see 100 roads in a city, 1 is closed. Here you can substitute 100 by every even number, such as 4.

For the second part, let $e$ be the number of edges, $f_4$ the number of quadrilaterals, $f_3$ be the number of triangles and $v$ the number of vertices. Notice that by the regularity you get the number of edges in terms of vertices. In particular, you have $$4v=2e. $$ By a similar double counting argument: $$3 f_3+4 f_4= 2e.$$ Then you can use Euler's formula, which says $$f_3+f_4-e+v=2.$$ You also know something more, every triangle is adjacent to three quadrilaterals and by summing up the quadrilaterals this way, you overcount by a factor of $4$. Hence, $$3 f_3 = 4 f_4.$$

Now we solve the system with the four equations. This gives $$\begin{align} f_3 & = 8,\\ f_4 &= 6, \\ e &= 24, \\ v&=12. \end{align} $$

Here is an example:

enter image description here

This is the graph of the cubeoctahedron. Should be the only possibilty.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.