Logout Open In App
Open In App
Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

Chapter 11: Q30SE (page 805)

Show that if every circuit not passing through any vertex other than its initial vertex more than once in a connected graph contains an odd number of edges, then this graph must be a cactus.

Short Answer

Expert verified

Therefore, the given statement is true. That is, every circuit not passing through any vertex other than its initial vertex more than once in a connected graph contains an odd number of edges, then this graph must be a cactus is true.

Step by step solution

Achieve better grades quicker with Premium

  • Unlimited AI interaction
  • Study offline
  • Say goodbye to ads
  • Export flashcards
Start your free trial Skip

Over 22 million students worldwide already upgrade their learning with Vaia!

01

General form

Definition of tree: A tree is a connected undirected graph with no simple circuits.

Definition of Circuit: It is a path that begins and ends in the same vertex.

Definition of rooted tree: A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.

Definition of Cactus: A cactus is a connected graph in which no edge is in more than one simple circuit not passing through any vertex other than its initial vertex more than once or its initial vertex other than at its terminal vertex(where two circuits that contain the same edges are not considered different).

02

Proof of the statement

Given that, a graph G is connected. Every simple circuit, that does not pass through any vertex (except the initial vertex) more than once, contains an odd number of edges.

To prove: G is a cactus.

Let G not be a cactus.

Then there exists an edge \(e = \left\{ {u,v} \right\}\) in G that is contained in two different simple circuits \({C_1}\) and \({C_2}\).

These simple circuits are then of the following form (where \({P_i}\) represents some path).

\(\begin{array}{l}{C_1} = u,{P_1},x,{P_2},y,{P_3},v,e,u\\{C_2} = u,{P_1},x,{P_4},y,{P_3},v,e,u\end{array}\)

Note:

  1. It is possible that \(u = x\)and/or\(v = y\), then the path between the two variables (that are the same) is non-existent.
  2. The two different circuits only differ in the path between x and y.

Since every simple circuit in G, that does not pass through any vertex (except the initial vertex) more than once, contains an odd number of edges, \({C_1}\) and \({C_2}\) both contain an odd number of edges.

Since \({C_1}\) and \({C_2}\) only differ in the paths \({P_1}\) and \({P_3}\), \({P_2}\) and \({P_4}\) both have to be odd or both have to be even.

However, we then obtain a simple circuit consisting of \({P_2}\) and \({P_4}\) backwards which needs to have an even number of edges, since the sum of two odd integers is even and the sum of 2 even integers is even too).

We have then derived a contradiction as G did not contain a simple circuit, that does not pass through any vertex (except the initial vertex) more than once, contains an odd number of edges.

Hence proved that G has to be a cactus.

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

Show that a center should be chosen as the root to producea rooted tree of minimal height from an unrooted tree.

Sollin's algorithm produces a minimum spanning tree from a connected weighted simple graph \({\bf{G = (V,E)}}\) by successively adding groups of edges. Suppose that the vertices in \({\bf{V}}\) are ordered. This produces an ordering of the edges where \({\bf{\{ }}{{\bf{u}}_{\bf{0}}}{\bf{,}}{{\bf{v}}_{\bf{0}}}{\bf{\} }}\) precedes \({\bf{\{ }}{{\bf{u}}_{\bf{1}}}{\bf{,}}{{\bf{v}}_{\bf{1}}}{\bf{\} }}\) if \({{\bf{u}}_{\bf{0}}}\) precedes \({{\bf{u}}_{\bf{1}}}\) or if \({{\bf{u}}_{\bf{0}}}{\bf{ = }}{{\bf{u}}_{\bf{1}}}\) and \({{\bf{v}}_{\bf{0}}}\) precedes \({{\bf{v}}_{\bf{1}}}\). The algorithm begins by simultaneously choosing the edge of least weight incident to each vertex. The first edge in the ordering is taken in the case of ties. This produces a graph with no simple circuits, that is, a forest of trees (Exercise \({\bf{24}}\) asks for a proof of this fact). Next, simultaneously choose for each tree in the forest the shortest edge between a vertex in this tree and a vertex in a different tree. Again the first edge in the ordering is chosen in the case of ties. (This produces a graph with no simple circuits containing fewer trees than were present before this step; see Exercise \({\bf{24}}\).) Continue the process of simultaneously adding edges connecting trees until \({\bf{n - 1}}\) edges have been chosen. At this stage a minimum spanning tree has been constructed.

Show that the addition of edges at each stage of Sollin’s algorithm produces a forest.

Devise an algorithm for constructing the spanning forest of a graph based on breadth-first searching.

Show that the first step of Sollin’s algorithm produces a forest containing at least \(\left\lceil {\frac{n}{2}} \right\rceil \) edges when the input isan undirected graph with \(n\) vertices.

How many edges must be removed from a connected graph with n vertices and m edges to produce a spanning tree?
See all solutions

Recommended explanations on Math Textbooks

Theoretical and Mathematical Physics

Read Explanation

Calculus

Read Explanation

Statistics

Read Explanation

Geometry

Read Explanation

Decision Maths

Read Explanation

Mechanics Maths

Read Explanation
View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free