Show that for a singly-connected graph the number of edges $E$ must be equal to the number of vertices minus $1$, $E=V-1$

Question

I am reading "Bayesian Reasoning and Machine Learning By David Barber". I am not completely sure how to do question 19 on page 23:

Show that for a connected graph that is singly-connected, the number of edges $E$ must be equal to the number of vertices minus $1$, $E=V-1$. Give an example graph with $E=V-1$ that is not singly connected.

Definition (Singly-Connected Graph). A graph is singly-connected if there is only one path from a vertex a to another vertex b. Otherwise the graph is multiply-connected. This definition applies regardless of whether or not the edges in the graph are directed. An alternative name for a singly-connected graph is a tree. A multiply-connected graph is also called loopy.

My approach to proving that $E=V-1$:

Proof by induction:

Let $P(n)$ be the statement that a singly-connected graph with $n$ vertices has $n-1$ edges.

We prove the base case, $P(1)$:

For a graph $G$ with $1$ vertex, it is clear that there are $0$ edges. (**Question 1:**Is this correct though, why can't there be $1$ or even $2$ edges such that this one vertex connects to itself with $1$ or $2$ paths respectively?)

We now prove the case for $P(n+1)$:

Suppose for the sake of induction that $P(n)$ is true. Let $G$ be a singly-connected graph with $n$ vertices and hence $n-1$ edges. Then if we add a vertex to $G$ with one edge connecting it to any of the vertices of $G$, then we have a new graph $G'$ which has $n+1$ vertices and $n$ edges.

Hence we have shown that $P(n)\implies P(n+1)$ and hence it it true for all $n\in \mathbb{N}$

Question 2: Would this proof be correct?

Question 3: I can't think of a graph which is not singly connected but has $E=V-1$ edges. What would be some examples?

Answer 1

For your question 1, as already noted by rici, you cannot have loops (edges connected a vertex to itself) in singly-connected graphs (which are often also called trees). In most graph textbook definitions in my experience as well, loops are not allowed.

For your question 2, also as noted by rici, your approach constructs a specific instance of P(n+1) so you do not prove that the the claim works for all instances of P(n+1).

In order to prove that this holds for any instance, you are right that you can work by induction but you must work in reverse: consider a tree with n+1 vertices. You must extract a tree with n vertices from it. The property holds for it because you have proven that it holds for all trees with n vertices. Then you must use the relationship between the two to show that the wanted property holds for the larger object.

In this case I would go like this: consider a tree with n+1 vertices. It's easy to show that it has at least one vertex with degree 1. Remove this vertex. You now have a tree with n node, and therefore with n-1 edges (by induction hypothesis). Your original n+1 vertex tree has one more vertex and one more edge, so it must have n+1 vertices and n edges, so the property holds for trees with n+1 vertices (notice that I did not make any assumption on the original tree with n+1 vertices I used so the proof is valid for any such tree).

Answer 2

$\underline{Answer1}$: Proof by induction

$Proof$: Let n be the number of vertices in a tree (T).

$~~~~~~~Base~cases$:

   If n=1, then the number of edges=0.

   If n=2 then the number of edges=1.

   If n=3 then the number of edges=2.

Hence, the statement (or result) is true for n=1, 2, 3.

Let the statement be true for n=m. Now we want to prove that it is true for n=m+1.

Let $E$ be the edge connecting vertices say $V_i$ and $V_j$. Since $G$ is a tree, then there exists only one path between vertices $V_i$ and $V_j$. Hence if we delete edge $E$ it will be disconnected graph into two components $G1$ and $G2$ say. These components have less than $m+1$ vertices and there is no circuit and hence each component $G1$ and $G2$ have $m1$ and $m2$ vertices.

     Now, the total no. of edges = (m1-1) + (m2-1) +1
                                 = (m1+m2)-1
                                 = m+1-1
                                 = m.

Hence for n=m+1 vertices there are m edges in a tree (T). By the mathematical induction the graph exactly has n-1 edges.

$\underline {Answer2}:$

The one you have done is other technic (also correct) but uses the same induction idea.

$\underline {Answer3}:$

A singly connected graph $G(V, ~E)$ is a directed graph which has at most 1 path from $u$ to $v$, $\forall$ $u,~v \in V$. So, a Non-singly graph would imply that the graph has atleast 2 paths from $u$ to $v$ (which could be formed by adding edges between the vertices to singly connected graph), hence number of vertices remain the same but not the edges (number of edged increases compared to singly connected), so $|E|>|V|-1$ for non-singly connected graph.

Hence you cannot come up with such graph.