0
$\begingroup$

Trying to solve this proof: proof any undirected loop-free graph on n vertices with at least (n-1)(n-2)/2 + 1 edges is connected. Give an example of a disconnected n-vertex graph with one fewer edge

I am not sure how to solve this one, I know that graphs with (n-1)(n-2)/2 edges are connected and then have assumed adding one edge would also leave this graph connected. When i prove by contradiction i end up with a disconnected graph unable to have k + 1 vertices and at least k(k-1)/2 + 1 edges, but feel that this is incorrect.

How to prove this and how to give an example with one fewer edge?

$\endgroup$
4
  • $\begingroup$ What do you mean by loop-free graph? Do you mean a forest? $\endgroup$ – Crostul Nov 27 '16 at 23:38
  • $\begingroup$ I guess you are also assuming that $G$ is a simple graph, i.e., any two vertices are joined by at most one edge? Otherwise, a disconnected graph on three vertices can have any number of edges. $\endgroup$ – bof Nov 27 '16 at 23:44
  • $\begingroup$ Loop free as in there is no loop on a single vertex (counts for 2 in deg) $\endgroup$ – lucyb Nov 27 '16 at 23:52
  • $\begingroup$ In that case here is a counterexample: take $3$ vertices $u,v,w$ and draw a million edges from $u$ to $v$. This is a disconnected loop-free graph. $\endgroup$ – bof Nov 27 '16 at 23:55
2
$\begingroup$

Suppose, to the contrary, that $G$ is disconnected. Then $G$ has at least two components. It suffices to prove the claim for when $G$ has exactly two components, $C_1$ and $C_2$ (think about why).

Suppose $|V(C_1)|=i$ and $|V(C_2)|=n-i$. The number of edges in $C_1$ is at most $\binom{i}{2}=\frac{i(i-1)}{2}$ (the number of edges in a complete graph with $i$ vertices), and the number of edges in $C_2$ is at most $\binom{n-i}{2}=\frac{(n-i)(n-i-1)}{2}$.

All you need to prove now is that for $1 \leq i \leq n-1$ $$\frac{i(i-1)}{2}+ \frac{(n-i)(n-i-1)}{2} \leq \frac{(n-1)(n-2)}{2}.$$

$\endgroup$
3
  • $\begingroup$ thanks but shouldn't there be a + 1 on the right hand side? $\endgroup$ – lucyb Nov 28 '16 at 0:10
  • $\begingroup$ @lucyb You need to find the $i$ that gives you equality in that inequality, which means that a disconnected graph can have $(n-1)(n-2)/2$ edges. This would show that a graph must then have $(n-1)(n-2)/2 + 1$ edges. Hope that helps! $\endgroup$ – Sarah Nov 28 '16 at 0:15
  • $\begingroup$ that helps, thanks! $\endgroup$ – lucyb Nov 28 '16 at 0:30
2
$\begingroup$

Hint. Suppose $G$ is a disconnected $n$-vertex graph. Then $G$ has a connected component with $r$ vertices for some $r$ with $1\le r\le n-1.$ Thus $G$ is a subgraph of the disconnected $n$-vertex graph $K_r+K_{n-r}$ which has $\binom r2+\binom {n-r}2$ edges. Now, what values of $r\in\{1,\dots,n-1\}$ maximize this number?

$\endgroup$
0

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.