# number of vertices in G

Let a graph has 6 components and 30 edges .what is the maximum possible number of vertices of G ? The problem seems to me interesting. Here each component may not have the same edges .Then how to approach the problem. I only know sum of the degree if all vertices = twice the number of edges. Any help would be appreciated. Thanks in advance.

## 1 Answer

Hint: A tree is a connected graph with no cycles. The following facts are useful:

• A tree with $n$ vertices must have $(n-1)$ edges
• A connected graph is a tree if and only if removing any edge will disconnect the graph

If we are to have as many vertices as possible, then each of the $6$ components of the graph must be a tree.

Suppose that the components have $E_1,E_2,\dots,E_6$ many edges respectively. The total number of edges is 30, which is to say that $$E_1 + E_2 + \cdots + E_6 = 30$$ Since each component is a tree, the number of vertices in the $i$th component must be $E_i + 1$. So, the total number of vertices is $$(E_1 + 1) + (E_2 + 1) + \cdots + (E_6 + 1)$$ which is necessarily $36$ (why?).

• I know all these facts.but I am sorry to say i cannot see how r these being used – math is fun Jun 15 '17 at 7:06
• Because each component is a tree, knowing the total number of edges is enough to figure out the total number of vertices. You're going to have to figure it out from there. – Omnomnomnom Jun 15 '17 at 7:09
• Here total no of vertices = 60.then? – math is fun Jun 15 '17 at 7:12
• No. Let's start here: why does the total number of vertices need to be less than 30? – Omnomnomnom Jun 15 '17 at 7:13
• @mathisfun If your graph has 6 components, then by drawing 5 more edges you can make it connected, right? So if you started with n vertices, 30 edges, and 6 components, you now have a connected graph with n vertices and 35 edges. What's the most vertices a connected graph with 35 edges can have? How many vertices does a tree with 35 edges have? – bof Jun 15 '17 at 10:27