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$

5 Answers 5

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$
1
  • $\begingroup$ Thank you ccorn. I understand it perfectly. thank you very much $\endgroup$
    – bece
    May 4, 2013 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$

You must log in to answer this question.

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