4
$\begingroup$

Let $n\ge2$ be an integer. Let $G$ be a graph with $n+1$ vertices and more than ${n \choose 2}$ edges. Show that $G$ is connected.

Here's my attempted solution to the above problem:

Induction on $n$:

Base case: $n=2$

So $n+1=3$ vertices. $\vert E\vert \gt {2 \choose 2} = 2$ so at least 3 edges, so connected.

Inductive step:

Assume $G$ connected for graph with $n+1$ vertices and $\vert E\vert \gt {n \choose 2}$ for all $n\ge2$.

Define $G\prime$ graph with $n+2$ vertices and $\vert E\vert \gt {n+1 \choose 2}$. Notice that $G\prime$ forms the complete graph $K_{n+1}$ with $n+1$ vertices and exactly ${n+1 \choose 2}$ edges (which is connected by IA). Now assume for contradiction that $G\prime$ is disconnected.

Since we need to use more edges than ${n+1 \choose 2}$ that are used for $K_{n+1}$, there is nowhere to else to add the edge back in other than between the complete graph and the vertex not included in it. We then obtain one connected component or a connected graph $G\prime$ which contradicts initial assumption. All graphs $G$ connected for $n\ge2$. (Q.E.D)

Is this proof correct?

Any tips, corrections, help would be greatly appreciated.

EDIT:

Removed use of removed vertex in proof. Instead, I rely solely on complete graph.

$\endgroup$
7
  • $\begingroup$ Hmm, there doesn't seem to be any question here. $\endgroup$ Commented Apr 16, 2019 at 20:13
  • $\begingroup$ @HenningMakholm My apologies, added the question. $\endgroup$ Commented Apr 16, 2019 at 20:16
  • $\begingroup$ Possible duplicate of How many edges are in a clique of n vertices? $\endgroup$
    – graeme
    Commented Apr 16, 2019 at 20:17
  • 1
    $\begingroup$ Justify this line: Remove one vertex from $G\prime$ so $G\prime\prime$ now has $n+1$ vertices and $\vert E \vert$ still greater than ${n\choose2}$. You have removed a node from your graph, so you have to also remove edges connected to that node. You are overcomplicating this though: you have a complete graph to start, and complete graphs must be connected. $\endgroup$ Commented Apr 16, 2019 at 20:19
  • 1
    $\begingroup$ Your proof attempt assumes that the only way it can be disconnected is by having a single disconnected node, which is incorrect. $\endgroup$
    – confucious
    Commented Apr 17, 2019 at 15:41

2 Answers 2

5
$\begingroup$

Here's a non-inductive proof. Suppose the graph is disconnected. That means that there exist 2 smaller disconnected from each other graphs of size $k$ and $l$, with $k+l = n+1$, and $l \ge 1$, $k \ge 1$. Let's then count the max number of edges we can have. Assume the two subgraphs are fully connected, then number of edges is:

$$\frac{k(k-1)}{2} + \frac{l(l-1)}{2} = \frac{n(n-1)}{2} - (k-1)(l-1) \le \frac{n(n-1)}{2}$$

Thus the graph has to be connected.

$\endgroup$
3
$\begingroup$

I am not seeing why $G''$ necessarily forms the complete graph on $n+1$ vertices.

This is how I would try it. Let $m$ be precisely the size of the largest connected component of $G$ [where $G$ is defined to be the graph on $n+1$ vertices with more than ${n \choose 2}$ edges].

If $m=n$ then $G$ can have at most ${n \choose 2}$ vertices [make sure you see why]. If $m \le n-1$ then use the fact that every vertex in $G$ can have degree at most $m-1$ [make sure you see this], so as $m$ satisfies $m \le n-1$ it follows that every vertex in $G$ can have degree at most $n-2$. So by the Handshaking Lemma there can be at most $\frac{(n-2)(n+1)}{2} \le {n \choose 2}$ [simple algebra to check]. Both of which contradict that $G$ has more than ${n \choose 2}$ edges.

$\endgroup$

You must log in to answer this question.

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