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
    Commented Nov 27, 2016 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
    Commented Nov 27, 2016 at 23:44
  • $\begingroup$ Loop free as in there is no loop on a single vertex (counts for 2 in deg) $\endgroup$
    – lucyb
    Commented Nov 27, 2016 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
    Commented Nov 27, 2016 at 23:55

2 Answers 2

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
    Commented Nov 28, 2016 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
    Commented Nov 28, 2016 at 0:15
  • $\begingroup$ that helps, thanks! $\endgroup$
    – lucyb
    Commented Nov 28, 2016 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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .