graph theory

Question

Answer 1

Explanation 2.11 

The graphs from which if any of the edges is deleted then the graph become disconnect such a graph called Trees

Such a tree is given in the diagram:-

 

Now according to the question if any of the edges is removed from the above graph then the graph become disconnect.

Explanation 2.12

Definition Required:-

Simple Graph: - Graph in there is no self-loop and no parallel edges are present then the graph is called simple graph.

Now take the above graph shown in explanation 2.11,

a) the graph was given is a simple graph.

b) the graph contain n-1 edges, where n is the no of vertices.

Comments

best example of 2.11 is bridge.

if we remove bridge from a connected graph, it becomes disconnected

Answer 2

The minimum number of edges a connected graph with n vertices will have is (n-1) . Now if we remove any of the edges,this graph will become disonnected.But they have given initailly the graph is connected.So our graph cannot have less than (n-1) edges.

Incase if we have more than (n-1) edges,then removing ANY EDGE from the graph will not guarantee disconnectivity,eventhough removal of some edges may guarantee disconnectivity.So our graph cannot have more than (n-1) edges. 

If a graph has multi-edges,then removal of any edge willnot guarantee disconnectivity,beacuse among the 2 vertives which has parallel edges,if i remove one of them other edges will ensure connectivity.So our graph cannot have multi-edges.

Similiarly,if my graph has self-loop,then removal of that self-loop edge will not make the connected graph disconnected.So our graph cannot have self-loops.

If our graph doesnot have multi-edges and self-loops,then it is definitely a simple-graph.