4
$\begingroup$

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!

2 Answers 2