3
$\begingroup$

A graph $G$ is connected if every pair of vertices in $u,v\in V$ is connected by some path.

For an undirected graph with $n$ vertices, how large does the edge set $E$ have to be to guarantee that it is connected?

I know for the complete graph $K_n$ has precisely $|E| = \frac{n(n-1)}{2}$ edges, but surely we do not need to consider every one of these to guarentee that $G$ is connected do we?

$\endgroup$
  • $\begingroup$ Think about how many edges you would have to remove from a complete graph to make it become disconnected. It seems clearer to view the problem from this direction. $\endgroup$ – mlg4080 Apr 29 '15 at 4:42
  • $\begingroup$ Well, assuming you were disconnecting a single vertex you would have to detach $n-1$ edges (where $n$ is the number of vertices) from the vertex. So to guarantee connection, you would need $\frac{n(n-1)}{2}-(n-2)$ edges? $\endgroup$ – Groups n' Stuff Apr 29 '15 at 4:50
2
$\begingroup$

HINT: Note that the disjoint union of $K_{n-1}$ and $K_1$ is a graph with $n$ vertices that is not connected, so you need more than $\frac12{(n-1)(n-2)}$ edges. This graph is missing just $n-1$ of the edges of the graph $K_n$. Suppose that you remove fewer than $n-1$ edges from $K_n$; can you disconnect the graph?

$\endgroup$
2
$\begingroup$

Consider $K_{n-1}$ plus an isolated vertex. How many edges are there so far?

Now what happens if you add an edge? Can the graph remain disconnected?

$\endgroup$

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.