# 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!

-

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).

-

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.

-