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!
Best Answer
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.