Proving a graph has no bridges 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!
 A: 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:

This is the graph of the cubeoctahedron. Should be the only possibilty.
A: 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.
