Cover and Independence Numbers of Paths and Cycles

Parameters of Paths and Cycles

Paths and cycles are simple enough to make their extremal sets visible, but their formulas still depend on parity. On a path, independent vertices can be chosen alternately from an endpoint. On a cycle, the choice must also respect the edge joining the last vertex to the first. We will calculate five parameters: the independence number, vertex-cover number, clique number, matching number, and edge-cover number.

All graphs in this tutorial are finite and simple. For $n\geq 1$, the path $P_n$ has vertices $1,\dots,n$ and edges $i(i+1)$ for $1\leq i<n$. For $n\geq 3$, the cycle $C_n$ has those path edges and the additional edge $n1$.

Definitions: An independent set is a set of vertices no two of which are adjacent; its largest possible size is the independence number $\alpha(G)$. A vertex cover is a set of vertices containing at least one endpoint of every edge; the smallest possible size is the vertex-cover number $\tau(G)$. A clique is a set of pairwise adjacent vertices; the largest possible size is the clique number $\omega(G)$. A matching is a set of edges with no shared endpoints; the largest possible size is the matching number $\nu(G)$. An edge cover is a set of edges such that every vertex is an endpoint of at least one selected edge; its smallest possible size is the edge-cover number.

An edge cover can exist only if the graph has no isolated vertices. Thus $P_1$, which has one vertex and no edges, has no edge cover, so its edge-cover number is undefined. Every $P_n$ with $n\geq2$, and every $C_n$ with $n\geq3$, has an edge cover.

The Formulas

Theorem: For a path $P_n$, $$ \alpha(P_n)=\left\lceil\frac n2\right\rceil,\qquad \tau(P_n)=\left\lfloor\frac n2\right\rfloor,\qquad \nu(P_n)=\left\lfloor\frac n2\right\rfloor. $$ For $n\geq2$, its edge-cover number is $\left\lceil n/2\right\rceil$. Its clique number is $1$ when $n=1$, and $2$ when $n\geq2$. For a cycle $C_n$, $n\geq3$, $$ \alpha(C_n)=\left\lfloor\frac n2\right\rfloor,\qquad \tau(C_n)=\left\lceil\frac n2\right\rceil,\qquad \nu(C_n)=\left\lfloor\frac n2\right\rfloor,\qquad \text{edge-cover number}=\left\lceil\frac n2\right\rceil. $$ Its clique number is $3$ for $C_3$, and $2$ for $C_n$ when $n\geq4$.

Proof. First, for any graph $G$, a vertex set $S$ is independent exactly when $V(G)\setminus S$ is a vertex cover. If $S$ is independent, an edge cannot have both endpoints in $S$, so every edge has an endpoint outside $S$. Conversely, if the complement is a vertex cover, no edge can have both endpoints in $S$. Taking a largest independent set and a smallest cover therefore gives $\tau(G)=|V(G)|-\alpha(G)$.

For $P_n$, selecting vertices $1,3,5,\dots$ gives an independent set of size $\lceil n/2\rceil$. To bound its size above, group the first $2\lfloor n/2\rfloor$ vertices into the adjacent pairs $\{1,2\},\{3,4\},\dots$. An independent set contains at most one vertex from each pair, and if $n$ is odd there is only one additional vertex. Thus its size is at most $\lceil n/2\rceil$, proving the formula for $\alpha(P_n)$. The complement identity gives $\tau(P_n)=n-\lceil n/2\rceil=\lfloor n/2\rfloor$.

For $C_n$, take an independent set $S$. Each vertex in $S$ has a successor around the cycle, and that successor is outside $S$. Distinct vertices have distinct successors, so $|S|\leq n-|S|$, which implies $|S|\leq\lfloor n/2\rfloor$. The vertices $1,3,\dots,n-1$ when $n$ is even, and $1,3,\dots,n-2$ when $n$ is odd, form independent sets of size $\lfloor n/2\rfloor$. Hence $\alpha(C_n)=\lfloor n/2\rfloor$, and the complement identity gives $\tau(C_n)=\lceil n/2\rceil$.

In either a path or a cycle, a matching with $k$ edges uses $2k$ distinct vertices, so $2k\leq n$ and $k\leq\lfloor n/2\rfloor$. Selecting $12,34,\dots,(2r-1)(2r)$, where $r=\lfloor n/2\rfloor$, gives a matching of that size in both graphs. (For a cycle these are among its edges.) This proves the matching formulas.

Any edge cover with $k$ edges can cover at most $2k$ vertices, so $k\geq\lceil n/2\rceil$. For even order $n=2r$, the edges $12,34,\dots,(2r-1)(2r)$ cover every vertex with $r=\lceil n/2\rceil$ edges. For odd order $n=2r+1$, use $12,34,\dots,(2r-1)(2r)$ and $2r(2r+1)$; these cover all vertices with $r+1=\lceil n/2\rceil$ edges. These edge sets are present in the path, and also in the cycle, proving both edge-cover formulas.

A path with at least two vertices has an edge, so its largest clique has size at least $2$. It has no triangle: among three vertices in a path, the first and last in path order are not adjacent. Thus no clique has more than two vertices. The graph $P_1$ has a single one-vertex clique and no larger set. In $C_3$, all three vertices are pairwise adjacent. In $C_n$ for $n\geq4$, each vertex has only its two cyclic neighbors, and those two neighbors are not adjacent to each other; hence there is no triangle. Since every cycle has edges, its largest clique then has size $2$. This proves all the claims. $\square$

Worked Examples

Worked Example: The Odd Path $P_5$

Let $V=\{1,2,3,4,5\}$ and $E=\{12,23,34,45\}$. The order is $n=5$. Substituting into the formulas gives $\alpha(P_5)=\lceil5/2\rceil=3$, $\tau(P_5)=\lfloor5/2\rfloor=2$, $\nu(P_5)=\lfloor5/2\rfloor=2$, and edge-cover number $\lceil5/2\rceil=3$. Also, $\omega(P_5)=2$.

Certificates for these values are the independent set $\{1,3,5\}$, the vertex cover $\{2,4\}$, the matching $\{12,34\}$, the edge cover $\{12,34,45\}$, and the clique $\{1,2\}$. The set $\{2,4\}$ covers $12,23$ at vertex $2$, and $34,45$ at vertex $4$. Each edge in the matching has separate endpoints. The three edge-cover edges meet all five vertices: $12$ meets $1,2$, $34$ meets $3,4$, and $45$ meets $5$ as well as $4$.

Check: The adjacent pairs $\{1,2\}$ and $\{3,4\}$ show that an independent set has at most one vertex from each pair, plus at most vertex $5$, so it has size at most $3$. The two disjoint edges $12,34$ force every vertex cover to have at least $2$ vertices. The matching bound is $\lfloor5/2\rfloor=2$, and an edge cover needs at least $\lceil5/2\rceil=3$ edges. The certificates attain all these bounds.

Worked Example: The Even Path $P_6$

Let $V=\{1,2,3,4,5,6\}$ and $E=\{12,23,34,45,56\}$. Since $n=6$, the formulas give $\alpha(P_6)=\lceil6/2\rceil=3$, $\tau(P_6)=\lfloor6/2\rfloor=3$, $\nu(P_6)=\lfloor6/2\rfloor=3$, and edge-cover number $\lceil6/2\rceil=3$. The clique number is $2$.

Take independent set $\{1,3,5\}$, vertex cover $\{2,4,6\}$, matching $\{12,34,56\}$, and edge cover $\{12,34,56\}$. The cover meets the five edges in order: $12$ at $2$, $23$ at $2$, $34$ at $4$, $45$ at $4$, and $56$ at $6$. The three selected edges have disjoint endpoints and together cover all six vertices. The edge $12$ is a clique of size $2$.

Check: The three disjoint pairs $\{1,2\},\{3,4\},\{5,6\}$ bound any independent set above by $3$. Each also forces a distinct vertex into any vertex cover, so a cover needs at least $3$ vertices. No matching can have more than $\lfloor6/2\rfloor=3$ edges, and no edge cover can have fewer than $\lceil6/2\rceil=3$ edges. The displayed sets meet each bound.

Worked Example: The Odd Cycle $C_5$

Let $V=\{1,2,3,4,5\}$ and $E=\{12,23,34,45,51\}$. Here $n=5$, so $\alpha(C_5)=\lfloor5/2\rfloor=2$, $\tau(C_5)=\lceil5/2\rceil=3$, $\nu(C_5)=\lfloor5/2\rfloor=2$, and the edge-cover number is $\lceil5/2\rceil=3$. Its clique number is $2$.

The independent set $\{1,3\}$ has no edge between its vertices. Its complement $\{2,4,5\}$ is a vertex cover: $12,23$ meet $2$; $34$ meets $4$; and $45,51$ meet $4,5$, respectively. A matching is $\{12,34\}$, and an edge cover is $\{12,34,45\}$. The latter covers vertices $1,2$, then $3,4$, then $5$. An edge such as $12$ is a clique of size $2$.

Check: For an independent set of size $k$, the successor argument around the cycle gives $k\leq5-k$, so $k\leq2$. A matching has at most $\lfloor5/2\rfloor=2$ edges, and an edge cover has at least $\lceil5/2\rceil=3$ edges. The three displayed edge and vertex sets attain the respective bounds; the complement of the independent set also confirms the cover size $5-2=3$.

Worked Example: The Even Cycle $C_6$

Let $V=\{1,2,3,4,5,6\}$ and $E=\{12,23,34,45,56,61\}$. The order is $n=6$. Thus $\alpha(C_6)=\lfloor6/2\rfloor=3$, $\tau(C_6)=\lceil6/2\rceil=3$, $\nu(C_6)=\lfloor6/2\rfloor=3$, the edge-cover number is $\lceil6/2\rceil=3$, and $\omega(C_6)=2$.

The set $\{1,3,5\}$ is independent, and its complement $\{2,4,6\}$ is a vertex cover. Indeed, the cycle edges alternate between a selected vertex in this cover and a vertex outside it. The edges $\{12,34,56\}$ form both a matching and an edge cover: they have pairwise disjoint endpoints and cover all six vertices. The adjacent pair $\{1,2\}$ is a clique.

Check: The cycle bound gives $|S|\leq6-|S|$ for every independent set $S$, hence $|S|\leq3$. A matching uses two vertices per edge, so it has at most $\lfloor6/2\rfloor=3$ edges; an edge cover needs at least $\lceil6/2\rceil=3$. The listed sets attain those bounds. The vertex-cover size also agrees with the complement calculation $6-3=3$.

Parity and Common Pitfalls

For paths, the two alternating choices can leave an unmatched endpoint when the order is odd. This is why the independent-set and edge-cover values round up, while the vertex-cover and matching values round down. For cycles, the closing edge changes the independent-set count: an odd cycle cannot select every other vertex all the way around without creating adjacent selected vertices. Consequently, the cycle’s independence number rounds down and its vertex-cover number rounds up.

Common mistake: treating a cycle like a path. On $C_5$, taking $\{1,3,5\}$ as an independent set would give three vertices, but $1$ and $5$ are adjacent through edge $51$. The correction is to check the closing edge as well as the consecutive path edges; for $C_5$, $\{1,3\}$ is independent and the formula gives $\lfloor5/2\rfloor=2$.

Another distinction: A matching is not an edge cover. A matching avoids shared endpoints, whereas an edge cover must reach every vertex and may use edges that share endpoints. For instance, the edge cover $\{12,34,45\}$ of $P_5$ has two edges sharing vertex $4$. The one-vertex path is also an important boundary case: it has a clique and an independent set of size $1$, but no edge cover because it has an isolated vertex.

Check Your Understanding

For each question, state the parameter value and give a short justification or certificate.

For $P_7$, find the independence number, vertex-cover number, matching number, edge-cover number, and clique number.
For $C_7$, give an independent set of maximum size and a vertex cover of minimum size.
Explain why the edge-cover number of $P_1$ is undefined, while that of $P_2$ exists.
Give a matching of maximum size in $C_8$, and use the vertex count to justify that it is maximum.
Why does the set $\{1,3,5\}$ fail to be independent in $C_5$, even though the corresponding alternating choice works in $P_5$?

Cover and Independence Numbers of Paths and Cycles

What You'll Learn

Parameters of Paths and Cycles

The Formulas

Worked Examples

Worked Example: The Odd Path \(P_5\)

Worked Example: The Even Path \(P_6\)

Worked Example: The Odd Cycle \(C_5\)

Worked Example: The Even Cycle \(C_6\)

Parity and Common Pitfalls

Check Your Understanding

Cover and Independence Numbers of Paths and Cycles

What You'll Learn

Parameters of Paths and Cycles

The Formulas

Worked Examples

Worked Example: The Odd Path \(P_5\)

Worked Example: The Even Path \(P_6\)

Worked Example: The Odd Cycle \(C_5\)

Worked Example: The Even Cycle \(C_6\)

Parity and Common Pitfalls

Check Your Understanding

Previous

Next