0
$\begingroup$

Let G be a graph with 15 vertices and 4 connected components. Prove that G has at least one component with at least 4 vertices. What is the largest number of vertices that a component of G can have?

Read over connected components for a long time and still have no idea how to prove this.

$\endgroup$
0
$\begingroup$

For the first, think about the pigeonhole principle. If each component has three vertices or less, how many vertices can there be? For the second, you want three of the components to have as few vertices as possible to leave as many as possible for the big one.

$\endgroup$
  • $\begingroup$ I haven't been taught the pigeon principle yet in my graph theory class yet. I don't think I can use it. $\endgroup$ – BuiZMath Jan 25 '18 at 14:41
  • $\begingroup$ Assume the contrary--that each of your components has less than 4 vertices. (So at most 3 vertices per component). What is your maximum possible number of vertices? What does this contradict? $\endgroup$ – Mauve Jan 25 '18 at 14:43
  • $\begingroup$ The pigeonhole principle is not part of graph theory, it is just about counting things. When stated, it seems obvious, but it is extremely useful. $\endgroup$ – Ross Millikan Jan 25 '18 at 15:19
  • $\begingroup$ @Useless I am still confused. Are you saying think about 15 vertices and there are 4 connected components. Then each vertex has at most 3 vertices? Why would this contradict ? :/ $\endgroup$ – BuiZMath Jan 25 '18 at 15:31
  • $\begingroup$ If each of the four components has three vertices the total number of vertices is $12$, so you can't have $15$. $\endgroup$ – Ross Millikan Jan 25 '18 at 15:33

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.