In der Graphentheorie bezeichnet ein Kaktusgraph (zum Teil auch nur Kaktus, manchmal auch Husimi-Baum) einen zusammenhängenden Graphen, in dem sich jedes Paar seiner Kreise höchstens einen gemeinsamen Knoten teilt.^[1]

Den Begriff Kaktusgraph (engl. cactus) führten Frank Harary und George Eugene Uhlenbeck ein.^[2] In dieser ursprünglichen Definition wurde jedoch verlangt, dass alle Kreise des Graphen Dreiecke sind.

• Ein Graph G ist ein Kaktusgraph genau dann, wenn die Anzahl seiner Zyklen seiner zyklomatischen Zahl ${\displaystyle \mu (G)}$ entspricht.
• Kaktusgraphen sind außerplanare Graphen.
• Jeder planare 3-zusammenhängende Graph besitzt einen aufspannenden Kaktusgraphen, der die Eigenschaft hat, dass das Entfernen eines beliebigen Knoten den Graphen in maximal zwei Zusammenhangskomponenten teilt.^[3]
• Die Familie aller Kaktusgraphen kann durch einen verbotenen Minor charakterisiert werden. Dieser Minor entspricht dem vollständigen Graphen ${\displaystyle K_{4}}$ in welchem eine Kante entfernt wurde.^[4]

1. ↑ Dennis Geller, Bennet Manvel: Reconstruction of cacti. In: Canad. J. Math. 21. Jahrgang, 1969, S. 1354–1360, doi:10.4153/CJM-1969-149-3 (englisch, math.ca [PDF]). 
2. ↑ Frank Harary, George E. Uhlenbeck: On the number of Husimi trees, I. In: Proceedings of the National Academy of Sciences. 39. Jahrgang, Nr. 4, 1953, Mathematical Reviews 0053893, S. 315–322, doi:10.1073/pnas.39.4.315 (englisch). 
3. ↑ Tom Leighton, Ankur Moitra: Some Results on Greedy Embeddings in Metric Spaces. In: Discrete & Computational Geometry. 44. Jahrgang, Nr. 3, 2010, S. 686–705, doi:10.1007/s00454-009-9227-6 (englisch, mit.edu [PDF]). 
4. ↑ Ehab El-Mallah, Charles J. Colbourn: The complexity of some edge deletion problems. In: IEEE Transactions on Circuits and Systems. 35. Jahrgang, Nr. 3, 1988, S. 354–362, doi:10.1109/31.1748 (englisch).