22
$\begingroup$

Show that every connected graph with $n$ vertices has at least $n − 1$ edges.

How can I prove this? Conceptually, I understand that the following graph has 3 vertices, and two edges:

a-----b-----c

with $a$, $b$ and $c$ being vertices, and $\{a,b\}$, $\{b,c\}$ being edges.

Is there some way to prove this logically?

--UPDATE--

Does this look correct? Any advice on how to improve this proof would be appreciated. Thank you.

pic

$\endgroup$
  • $\begingroup$ I'm not sure what background material you have to show this, but here is a hint: trees! One way to think of it is to consider the spanning tree of a connected graph. $\endgroup$ – angryavian Aug 1 '13 at 7:42
  • $\begingroup$ Do you know that every tree with $n$ vertices has exactly $n-1$ edges? $\endgroup$ – Brian M. Scott Aug 1 '13 at 7:43
  • $\begingroup$ I don't know... $\endgroup$ – user87509 Aug 1 '13 at 7:46
  • $\begingroup$ Prove by induction that every connected undirected graph with n vertices has at least n-1 edges. (But I am somewhat hesitant to close this as a duplicate of that question, since the OP in the other question was asking about specific hint he was given in his assignment.) $\endgroup$ – Martin Sleziak Aug 1 '13 at 8:12
  • $\begingroup$ "Also by Axiom 1, we can see that a graph with n-1 edges has one component, which implies that the graph is connected" - this is false. Axiom 1 states that a graph with n vertices and n-1 edges has AT LEAST n-(n-1)=1 component, NOT 1 component. The proof is almost correct though: if the number of components is at least n-m, that means n-m <= number of components = 1 (in the case of a connected graph), so m >= n-1. This is what you wanted to prove. $\endgroup$ – Cat Dec 29 '13 at 7:26
21
$\begingroup$

A graph with $v$ vertices and $e$ edges has at least $v-e$ connected components.

Proof: By induction on $e$. If $e=0$ then each vertex is a connected cmoponent, so the claim holds. If $e>0$ pick an edge $ab$ and let $G'$ be the graph obtained by removing $ab$. Then $G'$ has at most one component more than $G$ (namely if $a$ and $b$ are no longer in the same component in $G'$). By induction hypothesis, $G'$ has at least $v-(e-1)$ components, so $G$ has at least $v-(e-1)-1=v-e$ components as was to be shown.

$\endgroup$
5
$\begingroup$

There are two standard approaches:

  1. Use the spanning tree (and the fact that any tree of $n$ vertices has exactly $n-1$ edges).

  2. Induction on the size of the graph. Assume you have a connected graph of $n$ vertices and $m$ edges. Remove the edges until your graph splits in two parts. By inductive hypothesis both parts have at least $n_1 - 1$ and $n_2 - 1$ edges (where $n_1+n_2 = n$), so your graph had at least $n_1 -1 + n_2 - 1 + 1 = n - 1$ edges (the additional one denotes the last edge you removed before the graph stopped being connected).

I hope this helps $\ddot\smile$

$\endgroup$
  • $\begingroup$ How would you prove that such edge or edges exist for which Remove the edges until your graph splits in two parts. holds in every connected graph ? $\endgroup$ – Breaking Benjamin Jun 15 '18 at 0:25
  • $\begingroup$ @BreakingBenjamin You need to argue that 1) removing one edge splits the graph into at most 2 components and then 2) that two or more isolated vertices constitute a disconnected graph. Thus, when removing edges, there has to be a point where the first split happens. $\endgroup$ – dtldarek Jun 15 '18 at 7:44
5
$\begingroup$

Let $V = \{v_1, v_2, \dots, v_n\}$ be the set of vertices and consider the $n \times (n-1)$ triangle

$$ \begin{eqnarray} (v_1, v_2) & (v_1,v_3) & \cdots & (v_1, v_n) \\ & (v_2, v_3) & \cdots & (v_2,v_n) \\ & & & \; \; \; \; \vdots \\ & & & (v_{n-1}, v_n) \end{eqnarray}$$ where each point is associated with a potential edge. Circle an entry, say, if the graph does have an edge. If there are strictly less than $n-1$ edges, because there are $n-1$ rows there must be one of them without any edges. But a row is of the form $(v_i, v_j)$, $i<j$, and there being no edges on it means $v_i$ is not connected. But this means the graph isn't connected. So there are at least $n-1$ edges.

$\endgroup$
4
$\begingroup$

Let G be a connected Graph : If G has no cycles then G is connected with no cycles $=> G$ is a Tree. So $G$ has n-1 edges.

If G has cycles : and $G $ is connected then for every two vertices there is a path between them. Assuming that $G$ have only one cycle: lets look at the path : $ v_1,v_2 \dots v_n,v_1 $ we can remove the edge $ v_1,v_1$ and we will get a connected sub Graph $ v_1,v_2$ with no cycles and $E(H)+1 =E(G)$ so $E(G)=n$.

And by induction you will get that for every number of cycles n $E(G)\ge n$.

So if $G $ has cycles $E(G)=n-1$ else $E(G)\ge n$ .

$\endgroup$
  • $\begingroup$ Will you check my update and let me know if it's an acceptable proof? Thank you. $\endgroup$ – user87509 Aug 1 '13 at 10:28
1
$\begingroup$

This result is immediate by induction once you have established (as lemma) that in every connected graph with at least two vertices there are at least two vertices that can be individually removed (with all adjacent edges) such that the remaining graph is still connected. (The inductive proof applies removal of such a vertex.) The lemma itself in turn is proved by a fairly easy induction on the number of vertices.

$\endgroup$
0
$\begingroup$

Hint: Let $\Gamma$ be a connected graph. If $T \subset \Gamma$ is a maximal subtree, then $|E(\Gamma)| \geq |E(T)|$ and $|V(\Gamma)|=|V(T)|$. (Where $E(\cdot)$ and $V(\cdot)$ is the set of edges and vertices respectively.)

$\endgroup$
0
$\begingroup$

Consider any arbitrary vertex of the n vertices, call it vertex A. Since the graph is connected, there always exists atleast one simple path(without cycles) from vertex A to all vertices (excluding A). Now for consider two simple paths from A to B and A to C. If B is not same as C, there must be atleast one edge which is different in the two paths. Since atleast n-1(since n-1 vertices excluding A are present) paths exist, n-1 edges are must

$\endgroup$
  • $\begingroup$ There is a subtle gap in your proof. Although you show that two simple paths (leading to different destinations) must differ by "at least one edge", it is not immediately clear how one extends this to more than two paths. How would you exclude that $k$ paths might consist of different subsets of fewer than $k-1$ edges? $\endgroup$ – hardmath Jan 20 at 16:41
0
$\begingroup$

We can use Disjoint Sets here. Disjoint Set Data Structure aka Union-Find Data Structure is quite popular in Computer Science (Cycle Detection etc.).

Disjoint Sets of Vertices are very handy in defining connected components in a graph. The number of Disjoint Sets (DS) equals the number of connected components. $v,u \in V$ are members of same DS if there is a path from $u$ to $v$.

To construct DSs of a graph, we start with $|V|$ Sets with each $v\in V$ representing a DS. Then we add the edges information. For each $\{v,u\} \in E$, we find the DSs to which $v$ and $u$ belong and union the two sets if they lie in different DSs. So for each edge, there is either $1$ or $0$ union operation.

In this setting, since the graph is connected, we must have a single DS at the end. To merge $|V|$ DSs to one, we must have $|V|-1$ Union operations. Hence at least $|V|-1$ edges are required.

Generalisation : If a graph has $k$ connected components, we must have $|V|-k$ union operations. Hence, $|E| \geq |V|-k$ or $|E|+k \geq |V|$

$\endgroup$
  • 1
    $\begingroup$ "Disjoint Sets of Vertices are very handy in defining connected components in a graph." It actually seems to be the same definition. Perhaps the Disjoint Sets nomenclature is more common ("quite popular") in Computer Science, but the term connected components is conventional in mathematics. Stripped to its basics, your post gives a correct proof that the number of components plus the number of edges is greater than or equal to the number of vertices. There is room for improvement in presentation. $\endgroup$ – hardmath Jan 20 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy