1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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?).

$\endgroup$
  • $\begingroup$ I know all these facts.but I am sorry to say i cannot see how r these being used $\endgroup$ – math is fun Jun 15 '17 at 7:06
  • 1
    $\begingroup$ 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. $\endgroup$ – Omnomnomnom Jun 15 '17 at 7:09
  • $\begingroup$ Here total no of vertices = 60.then? $\endgroup$ – math is fun Jun 15 '17 at 7:12
  • $\begingroup$ No. Let's start here: why does the total number of vertices need to be less than 30? $\endgroup$ – Omnomnomnom Jun 15 '17 at 7:13
  • $\begingroup$ @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? $\endgroup$ – bof Jun 15 '17 at 10:27

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.