0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.