StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q39SE

Expert-verifiedFound in: Page 738

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**Show that a graph is not orientable if it has a cut edge.**

It is proved that the graph having a cut edge can’t be orientable.

**If there is an orientation (a set of arc directions) that makes D strongly linked and there is a directed path between every pair of vertices, the graph is said to be orientable.**

Assume that the undirected graph G has a cut edge *a, b*.

When the edge is eliminated, *a* and *b* become independent components of G; in other words, all paths from *a* to *b* must pass through the edge in the *a* to *b* direction, and all paths from *b* to *a* must pass through the route in the *b* to *a* direction.

Assume that we know the graph's orientation.

If *a, b*are oriented as *(a, b)*, then there can't be a path from *b* to *a*in the resulting directed graph.

Hence, the resulting directed graph isn't strongly linked, as observed.

If *a, b*, on the other hand, is orientated as *(b, a),* then there can't be a path from *a* to*b* in the resultant directed graph.

As a result, G is not orientable by definition.

Intriguingly, the inverse of this conclusion is also true.

Thus, it is proved that the graph having a cut edge can’t be orientable.

94% of StudySmarter users get better grades.

Sign up for free