Cycles and Chords
A cycle may have extra edges between its vertices, even when those edges are not part of the cycle itself. Those extra edges matter when identifying chordal graphs: the relevant obstruction is not simply a long cycle, but a cycle whose vertices have no such extra adjacencies. This distinction is especially useful when studying graph properties that are defined through induced subgraphs.
All graphs in this tutorial are finite and simple. A cycle of length \(\ell\) is a sequence \(v_1,v_2,\dots,v_\ell,v_1\), where \(\ell\ge 3\), the vertices \(v_1,\dots,v_\ell\) are distinct, and consecutive vertices (including \(v_\ell,v_1\)) are adjacent. Two vertices of the cycle are consecutive if they are joined by one of its cycle edges.
For a vertex set \(S\subseteq V(G)\), the induced subgraph \(G[S]\) has vertex set \(S\) and contains every edge of \(G\) whose two endpoints belong to \(S\). Thus, deciding whether a particular cycle is induced requires checking all possible edges between its vertices, not just checking that the listed cycle edges exist. Every triangle is induced in a simple graph: each pair of its three vertices is consecutive on the triangle, so there is no nonconsecutive pair that could form a chord.
A Cycle Characterization
Proof. Suppose first that \(G\) is chordal. If a cycle of length at least \(4\) had no chord, it would be an induced cycle of length at least \(4\), contradicting the definition of chordal. Hence every such cycle has a chord.
Conversely, suppose every cycle of length at least \(4\) has a chord. An induced cycle of length at least \(4\) would be a cycle with no chord, contradicting this assumption. Therefore \(G\) has no induced cycle of length at least \(4\), which is exactly the definition of chordal. The two implications prove the equivalence. \(\square\)
The theorem allows two equivalent ways to check chordality. One can look for an induced cycle of length at least \(4\), or examine cycles of length at least \(4\) and check that each has a chord. In examples, listing the cycles is practical when the graph is small. The statement does not say that every cycle must be induced; chordal graphs can have long cycles, provided those cycles have chords.
Worked Example: A Chordless 5-Cycle
Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,34,45,15\}\). These edges form the cycle \(1,2,3,4,5,1\). Determine whether \(G\) is chordal.
The cycle uses all five vertices. Its nonconsecutive pairs are \(13,14,24,25,35\). None is in \(E\): the full edge set is \(12,23,34,45,15\). Thus this 5-cycle has no chord and is induced.
In fact, it is the only cycle in this graph. Each vertex has exactly two incident edges, so once a cycle uses any vertex it must use both of that vertex’s incident edges; continuing around the graph forces all five edges. The cycle is induced and has length \(5\ge4\), so \(G\) is not chordal.
Check: the cycle’s five edges are exactly the edges induced by its five vertices, since those vertices are all of \(V\). This verifies directly that the cycle is induced.
Worked Example: A Cycle with a Chord Is Not the Whole Test
Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,34,45,15,13\}\). The edges \(12,23,34,45,15\) give the 5-cycle \(1,2,3,4,5,1\), and \(13\) is a chord of that cycle. Decide whether \(G\) is chordal.
First, the 5-cycle is not induced, because \(13\) joins two nonconsecutive vertices of it. But there is another cycle: \(1,3,4,5,1\), of length \(4\). Its cycle edges are \(13,34,45,15\). The other pairs among its vertices are \(14\) and \(35\); neither belongs to \(E\). Therefore this 4-cycle is induced, and \(G\) is not chordal.
For completeness, the cycles in this graph are the triangle \(1,2,3,1\), the 4-cycle \(1,3,4,5,1\), and the 5-cycle \(1,2,3,4,5,1\). To see that the list is exhaustive, vertex \(2\) has neighbors only \(1\) and \(3\), so a cycle using \(2\) must use the segment \(1,2,3\). It can close immediately by \(31\), giving the triangle, or continue along \(3,4,5,1\), giving the 5-cycle. A cycle not using \(2\) must use vertices from \(\{1,3,4,5\}\); the edges on these vertices are exactly \(13,34,45,15\), which give the listed 4-cycle. The 5-cycle has chord \(13\), but the 4-cycle has none.
Check: the induced subgraph on \(\{1,3,4,5\}\) has exactly four edges, \(13,34,45,15\). These are exactly the edges of the 4-cycle, confirming that it is induced. A chord in one cycle therefore does not rule out a different induced cycle.
Worked Example: A Chordal Graph with a 4-Cycle
Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,13,14,23,24\}\). This is the complete graph on four vertices with the edge \(34\) omitted. Determine whether \(G\) is chordal.
The triangles are \(1,2,3,1\) and \(1,2,4,1\). Both are induced, as every triangle in a simple graph is induced. The only 4-cycle is \(3,1,4,2,3\): its edges are \(13,14,24,23\). Its nonconsecutive vertex pairs are \(12\) and \(34\). The edge \(12\) is present, so it is a chord; \(34\) is absent.
There are no cycles longer than \(4\), because the graph has only four vertices. The 4-cycle has a chord, and there is no induced cycle of length at least \(4\). Thus \(G\) is chordal, even though it contains a 4-cycle.
Check: the edge set contains five edges, and the listed cycle uses four of them. The remaining edge is \(12\), joining the nonconsecutive vertices \(1\) and \(2\) of that cycle, so the cycle is not induced.
Induced Subgraphs Preserve Chordality
Proof. Let \(G\) be chordal, and let \(S\subseteq V(G)\). We must show that \(G[S]\) has no induced cycle of length at least \(4\). Suppose, to the contrary, that \(G[S]\) has such a cycle \(C\), with vertex set \(T\subseteq S\). Because \(G[S]\) is induced, it contains every edge of \(G\) whose endpoints are in \(S\). Because \(C\) is induced in \(G[S]\), there is no edge of \(G[S]\) between nonconsecutive vertices of \(C\). Any edge of \(G\) between two vertices of \(T\) would also be an edge of \(G[S]\), since \(T\subseteq S\). Therefore there is no edge of \(G\) between nonconsecutive vertices of \(C\), so \(C\) is an induced cycle in \(G\). Its length is at least \(4\), contradicting that \(G\) is chordal. Hence \(G[S]\) is chordal. If \(S\) is empty or has fewer than four vertices, it cannot contain a cycle of length at least \(4\), so the conclusion holds in those cases as well. \(\square\)
The proposition depends on taking an induced subgraph. If vertices are selected and some edges between them are then discarded, the result is an ordinary subgraph, not necessarily an induced subgraph. Removing such edges can turn a cycle that had a chord into an induced cycle. The closure statement above is specifically about retaining all edges among the selected vertices.
Common Pitfalls and How to Avoid Them
Confusing a cycle with an induced cycle. The 5-cycle in the second example is a cycle, but it is not induced: the extra edge \(13\) is a chord. Conversely, finding a chord in that cycle does not prove the graph chordal, since the different cycle \(1,3,4,5,1\) is induced. To classify the graph, every cycle of length at least \(4\) must have a chord, or equivalently one must rule out every induced cycle of that length.
Checking only the edges listed in the cycle. For a proposed cycle, write down all pairs of its vertices that are nonconsecutive, then check whether any of those pairs is an edge. For example, the cycle \(3,1,4,2,3\) has cycle edges \(13,14,24,23\), but checking only those four edges would miss its chord \(12\).
Assuming chordal graphs have no long cycles. The third example is chordal and has a 4-cycle. Chordal means that every cycle of length at least \(4\) has at least one chord; it does not mean that cycles of those lengths are absent.
Induced-cycle checks are a way to express graph structure through the adjacencies among a chosen set of vertices. This is why induced subgraphs are central in the study of chordal graphs and perfect graphs. The examples also show why the exact condition matters: a single induced cycle of length at least \(4\) is enough to disprove chordality, while a chord in one particular cycle is not enough to establish it.
Check Your Understanding
For each question, distinguish the edges of the proposed cycle from possible chords.
- Let \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41,13\}\). Is the cycle \(1,2,3,4,1\) induced? Is the graph chordal?
- Explain why every triangle in a simple graph is induced.
- Give the definition of a chordal graph using induced cycles, and restate it using chords of cycles.
- Why does an induced cycle in \(G[S]\), where \(G[S]\) is an induced subgraph, also give an induced cycle in \(G\)?
- Can a chordal graph contain a cycle of length \(5\)? State the condition that such a cycle must satisfy.