Suppose G is a graph with 2 connected components, both being Eulerian. What is the minimum number of edges that need to be added to G to obtain a connected Eulerian graph?
I started by considering two different cases regarding the completeness of G, but I'm stuck there. Can anyone help me out?
$C_{1}$ and $C_{2}$ are connected, Eulerian components, thus their every vertex has even degree.
If there exist vertices $x,y,z$ such that $x\in C_{1}$, $y\in C_{2}$ and $xz,yz\notin E(G)$, then creating edges: $xy, xz, yz$ will get you an Eulerian graph, because all the vertices still have even degree (you added two neighbors to each of these three vertices). You cannot create an Eulerian cycle using less edeges, because then you get a graph with at least one vertex with odd degree. And such graph is not Eulerian.
If $C_{1}$ and $C_{2}$ are complete, then you need to create exactly four edges, namely $xy, uv, xu, yv$ for $x,u\in C_{1}$ and $y,v\in C_{2}$. It obviously works, because you get proper degrees, but to show that you can't do better you can show that you can't make all the degrees even by adding one, two or three edges.