56.- Show that if G connected then (Hint: consider the spanning tree of G) Show

Question

56.- Show that if G connected then (Hint: consider the spanning tree of G) Show that if G connected then |E(G)| |V(G)|-1 (Hint: consider the spanning tree of G)

Explanation / Answer

Given the graph G is connected. E(G) represent the set of edges. V(G) represents the set of vertices. Now if the graph is connected, there should be a spanning tree forG> This is because if a graph is connected, there will be a pathfrom every edge to every other edge. consider the spanning tree.....This is a tree and there will be aroot. All the vertices in the spanning tree must be connected. Ina tree to connect V(G) vertices we need V(G)-1 edges. We know that E(G) >= the number of edges in the spanningtree Therefore E(G) >= V(G)-1

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.