Let $G = (V, E)$ be a simple undirected graph with $v$ vertices and $e$ edges.
A simple undirected graph G is called acyclic if it does not contain any cycle subgraph. A simple undirected graph G is called a tree if it is connected and acyclic. Show that every two trees with the same number of vertices must have the same number of edges
Can someone help me to solve the above parts? I am getting no idea.
For a graph to be connected, there must exist a path from one vertex to another. So, if a graph is connected, an absolute necessity must be that every vertex have an edge incident on it. Use this to get the first part.
For the second part, observe that the condition mentioned in the previous paragraph is hardly sufficient. If you can figure out why it is not sufficient, then you should get the answer to this.
A way to do the third part is to use induction. Induct on the number of vertices, and remove a vertex of suitable degree that will give you a favourable result for the induction hypothesis. However, it is also an immediate consequence of the first part. Use the definition of connectedness between two vertices.
Again, the fourth part is a consequence of the previous parts. It should help to actually look at a tree and see why it is true. The third part gives a nice characterisation of acyclic graphs, the first part gives one for connected graphs. Combine the two.