This paper introduces an efficient algorithm for detecting triangles in undirected graphs with a time complexity of O (n + m), where n is the number of vertices and m is the number of edges. By avoiding costly matrix multiplications, the method is particularly effective for sparse graphs. We provide a rigorous proof of correctness, ensuring all triangles are identified without omissions or duplicates, and validate the algorithm's linear-time performance. This advancement enhances sparse graph analysis, enabling faster triangle detection, clustering coefficient computation, and community detection. Applications include social network analysis, bioinformatics, and recommendation systems, making it a practical tool for studying large-scale networks and their properties.
Frank Vega (Tue,) studied this question.