1
$\begingroup$

I should prove this claim:

Every undirected graph with n vertices and $2n$ edges is connected.

If it is false I should find a counterexample. I was thinking to consider the complete graph with $n$ vertices. Such a graph is connected and contains $\frac{n(n-1)}{2}$ nodes. Considering that $2n > \frac{n(n-1)}{2}\implies$ my graph is connected too. But I'm not sure this could be a solution because even my graph has $2n$ edges it doesn't have to be complete. Can anybody help me?

$\endgroup$
2
$\begingroup$

Consider two copies of graphs with $m$ vertices amd $2m$ edges, e.g. of $K_5$, the complete graph with $m=5$ vertices. With two copies, you have $n=2m$ vertices and $2n$ edges, but the graph is not connected. Therefore the claim is false.

$\endgroup$
  • $\begingroup$ Thank you ccorn. I understand it perfectly. thank you very much $\endgroup$ – bece May 4 '13 at 9:54
1
$\begingroup$

Hint: Suppose you have a non-empty graph $G$ with $n$ vertices and $2n$ edges, how many edges and vertices does $G\coprod G$ have? Is it connected?

$\endgroup$
1
$\begingroup$

How might you prove or give a counter-example? What does it mean for a graph to be connected?

You observe that the number of edges in a complete graph is $\cfrac {n(n-1)}{2}$, and this grows faster than $2n$. So large complete graphs will have many more edges than $2n$.

You might also know that the minimum number of edges to make a connected graph with $n$ vertices is $n-1$ (a tree). So if need be we can delete quite a lot of edges from our complete graph and still leave it connected. So we can create a connected graph with some flexibility on the number of edges, but just deleting edges from a complete graph could leave the result connected. If deleting edges looks a bit tricky, let's try to add a disconnected component to this and still end up with $2n$ edges.

Now the complete graph on 5 vertices has 10 edges, so we've no flexibility there. But when we go up to 6 vertices, we find 15 edges, and we note that this is greater than $2\times 7=14$.

So we can take a complete graph on 6 vertices, add a single vertex, to make 7, and delete one edge to give 14. And we have a disconnected graph with $2n$ edges.

$\endgroup$
0
$\begingroup$

This is false. Suppose $2n=\binom{k}{2}$ for some $k$ and $n>k$. Take a complete graph with $k$ vertex together with $n-k$ isolated vertex, then you get a graph with $n$ vertex and $2n$ wedges.

$\endgroup$
0
$\begingroup$

The claim is true for up to $6$ vertices. The smallest counterexample (unique up to isomorphism) is this graph on $7$ vertices:

Smallest counterexample

The vertices are ascribed their degree, so we can easily verify there are $14$ edges via the Handshaking Lemma.

For $n \geq 8$ there always exists counterexamples; we add $n-7$ vertices and connect them to the two blue vertices above, thereby adding $2(n-7)$ edges.

$\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.