Bipartite Connected Graph, Eulerian Circuit

bipartite-graphseulerian-pathgraph theory

Give an example of a bipartite connected graph which has an even number of vertices and an Eulerian circuit, but does not have a perfect matching.

Bipartite ... Only Red and Blue vertices are joined.

An even number of vertices ... $3+5=8$.

Eulerian ... each vertex has even valency.

But ... there is clearly no matching.

Here is a $2$-regular graph that is not connected:

             o---o   o---o  
             |   |   |   |  
             o---o   o---o

Your reasoning about (b) and (c) is correct; (c) is the only one that must have an Euler circuit.

Here we go: $$\huge\cdot\qquad\cdot$$

remember that $0$ is even. The circuit is the "empty circuit"
Since the graph has no edges, we've already passed every edge if we don't even move :D