Graph problem, euler circuit and planar

Question

a connected planar graph G has 20 vertices, seven of which have degree l. Prove that G has at most 40 edges.

b Suppose a graph has 4 connected components and all vertices have even degrees. What is the minimum. number of edges that need to be added such that the graph has an Euler circuit?

c In general, given a graph, describe a method to add the minimum number of edges such that the graph has an Euler circuit. Illustrate your method with a graph which has '10 connected components, and the number of vertices with odd degrees in each component is as follows: 0,2,2,4,6,8,8,10,10,12. What is the total number of edges added?

Sorry for putting questions that I am confused about together because they require similar concepts

Answer 1

a) We have seven vertices of degree $1$. The edges incident to these vertices are calculated twice in $\sum_{v \in V(G)} deg(v)$. It suffices to consider the induced subgraph of the remaining $13$ vertices (as we have already counted any incidences to the remaining vertices of degree $1$). As $G$ is planar, the remaining $13$ vertices induce a planar graph. Thus, the number of edges in the induced subgraph is at most $3(13) - 6 = 33$. We then add the remaining $7$ edges from the vertices of degree $1$.

b) You need to connect the four components and ensure all vertices have even degree (by the characterization of Eulerian circuits).

c) Expand on your answer from (b).

Give it a try and let us know where you're getting stuck. Good luck!