 [Graph Theory - Discrete Mathematics] How do you solve this? Let G=(V,E) be a co CMIIh 2021-08-16 Answered
[Graph Theory - Discrete Mathematics] How do you solve this?
Let $$\displaystyle{G}={\left({V},{E}\right)}$$ be a connected simple graph, and call the edge $$\displaystyle{\left({u},{v}\right)}\in{E}$$ essential if the graph obtained by removing (u, v) from G is disconnected. Show that G is a tree if and only if all its edges are essential.

Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it Sally Cresswell
Step 1
Given
Let $$\displaystyle{G}={\left({V},{E}\right)}$$ be a connected simple graph, and call the edge $$\displaystyle{\left({u},{v}\right)}\in{E}$$ essential if the graph obtained by removing (u,v) from G is disconnected.
Step 2
Solution
To show that G is a tree if and only if all its edges are connected.
Since, all vertices in a tree are path connected with a unique path in between them.
So removing an edge from the graph will make it disconnected or just as two distinct subgraphs.
Thus, easily conclude that G is a tree if and only if all its edges are essential.