0
$\begingroup$

prove that every graph $G$ on $\{1,2,\cdots,n\}$ which is acyclic and has $n-2$ edges has exactly $2$ connected components

If it was $n-2$ then the graph was a tree which has exactly 2 connected components. But I have no idea for $n-2$ edges. I was wondering what can we say about for $n-k$ edges where $k<n?$

$\endgroup$
0
0
$\begingroup$

HINT: Each component of an acyclic graph is a tree. Suppose that the graph has $m$ components, $C_1,\ldots,C_m$, and for $k=1,\ldots,m$ let $n_k$ be the number of vertices in $C_k$, so that $n_1+\ldots+n_m=n$.

  • If $1\le k\le m$, how many edges does $C_k$ have?
  • How many edges does the graph have altogether?

So what, in general, is the relationship between the number of components of an acyclic graph on $n$ vertices and its number of edges?

$\endgroup$
4
  • $\begingroup$ Each component of an acyclic graph is a tree then isn't there should be $k-1$ edges for each $C_k?$ There should be $\frac{m(m-1)}{2}={}^mC_2$ edges altogether. @Brian M. Scott $\endgroup$ Apr 13 '21 at 23:02
  • $\begingroup$ @WhyGraph_: Not $k-1$ edges: $n_k-1$ edges. That makes a total of $$\sum_{k=1}^m(n_k-1)$$ edges; now simplify that sum to get something that involves only $n$ and $m$. $\endgroup$ Apr 13 '21 at 23:06
  • $\begingroup$ $$\sum_{k=1}^m(n_k-1)=\sum_{k=1}^mn_k-\sum_{k=1}^m1=n-m$$ Aha, I get it. Thanks @Brian M. Scott $\endgroup$ Apr 13 '21 at 23:09
  • $\begingroup$ @WhyGraph_: Yep, you’ve got it; you’re welcome. $\endgroup$ Apr 13 '21 at 23:16

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.