Question

Which of these graphs are cacti?

Short answer

Part (a): Therefore, the given graph is cactus.

Part (b): Therefore, the given graph is not a cactus.

Part (c): Therefore, the given graph is cactus.

Step-by-step solution

General form

Definition of tree: A tree isa 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).

Evaluate the graphs

Given that, the graphs.

Part (a):

Given graph is,

We notice that the given graph contains only one simple circuit. That is, the triangle at the bottom.

Then, it is not possible for an edge to be present in more than one simple circuit.

Conclusion: So, the given graph is a cactus.

Part (b):

Given graph is,

We notice that the given graph contains 3 simple circuit. That is, the 2 trianglesand a square.

And the square and one of the triangle shares one edge, thus one edge is in more than one simple circuit.

Conclusion: So, the given graph is not a cactus.

Part (c):

Given graph is,

We notice that the given graph contains 3 simple circuit. That is, the triangles at the top, middle and bottom.

Then, the triangles share an edge, thus none of the edges is in more than one simple circuit.

Conclusion: So, the given graph is a cactus.