I have seen this question, however I don't think it exactly applies to my 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?
Best Answer
Re Q2:
Your proof is not completely correct. The statement $P(n+1)$ that you want to prove is that every tree with $n+1$ vertices has $n$ edges.
In your proof you have constructed some $G'$ from $G$ by adding a vertex, so you have only proved that for any $n$ there is some tree with $n+1$ vertices and $n$ edges. But maybe there is a tree graph that cannot be constructed in that way? That tree graph would not be part of your proof and so might have a different number of edges.
To prove the result properly, you have to show that for any tree $G'$ with $n+1$ vertices, there is at least one vertex that you can remove to get a tree $G$ with $n$ vertices, thereby showing that $G'$ can actually be constructed from $G$ by adding that vertex again.