Although this seems rather obvious, I couldn't prove it rigorously. Any ideas how to prove it? The graph is assumed to be simple and connected.
Explanation of the terms:
- $k$-regular means that all vertices have degree $k$;
- bipartite means that there are 2 sets of vertices $X, Y$, where vertices from $X$ only have edges with vertices $Y$ and vertices from $Y$ only have edges with vertices from $X$;
- cut-edge is an edge which removal disconnects the graph;
This is b) part of the exercise, maybe a) part can help:
a) If all vertices $v \in G$ have an even degree, $G$ does not have cut-edge
From a) it actually follows that for even $k$, b) is true, thus only case with odd $k$ left to prove.