4cycles

4cycles is a term used in graph theory to refer to a 4-cycle, also known as a C4. A 4-cycle is a simple cycle consisting of four distinct vertices v1, v2, v3, v4 connected in sequence by edges v1–v2, v2–v3, v3–v4, and v4–v1, forming a closed loop that visually resembles a square. In a larger graph, these four vertices may appear as a subgraph; if there are additional edges among them, the subgraph is not necessarily an induced C4, but the cycle itself remains a 4-cycle within the graph.

Counting and detection of 4cycles is a common task in graph analysis. A practical approach examines pairs of vertices and the number of distinct two-edge paths between them; every pair with at least two such paths yields a potential 4cycle. A widely used method involves counting common neighbors: if two vertices share two or more common neighbors, those neighbors together with the pair form a 4cycle. For large or dense graphs, matrix-based techniques using adjacency matrices and their powers provide efficient ways to estimate or count 4cycles, alongside algorithmic methods that scale with the graph’s size and structure.

Significance and applications of 4cycles appear in several areas. In network topology, they help describe square-like patterns of connections. In chemistry, analogous four-membered ring structures are studied as part of cyclic compounds. In extremal and structural graph theory, researchers investigate how many edges a graph on n vertices can have without containing a 4cycle, with the extremal number ex(n, C4) known to grow on the order of n^{3/2}. The concept also relates to properties of bipartite graphs and lattice models.

4cycles is closely related to C4 and the square graph, and is distinguished from longer even cycles such as C6 or C8. In counting, distinctions between induced and non-induced subgraphs affect results and methods.