3-regular graphs with no bridges
Solution 1:
Hint: To use Tutte's theorem, we must show that the graph satisfies Tutte's condition; that is, for any $S\subset V(G)$, we must show that $q(G-S) \leq |S|$, where $q(G-S)$ denotes the number of odd components in $G-S$. Consider an arbitrary set $S\subset V(G)$ and look at an odd component $C$ of $G-S$. What can you say about the number of edges running between $C$ and $S$?
Solution 2:
What your are being asked to prove is sometimes known as Petersen's Theorem.