Why These Families Are Useful
Paths, cycles, and complete bipartite graphs are small enough to analyze directly, yet they display several patterns that recur throughout graph theory. On a path, the two endpoints behave differently from the internal vertices. On a cycle, closing the path creates a parity condition. In a complete bipartite graph, the two parts determine both adjacency and degree. We will calculate the independence number, clique number, chromatic number, and degree parameters for each family.
All graphs in this tutorial are finite and simple. A path \(P_n\) has vertices \(1,\dots,n\) and edges \(i(i+1)\) for \(1\le i<n\), where \(n\ge1\). A cycle \(C_n\) has vertices \(1,\dots,n\) and edges \(12,23,\dots,(n-1)n,n1\), where \(n\ge3\). A complete bipartite graph \(K_{a,b}\), with \(a,b\ge1\), has two disjoint parts \(A\) and \(B\), of sizes \(a\) and \(b\), and every possible edge between the parts, with no edges within either part.
Formulas for the Three Families
The complete set of formulas is summarized below. The path cases include the single-vertex graph. Cycle lengths start at \(3\), and both part sizes of \(K_{a,b}\) are positive.
| Graph | \(\alpha\) | \(\omega\) | \(\chi\) | Degrees |
|---|---|---|---|---|
| \(P_n\) | \(\lceil n/2\rceil\) | \(1\) if \(n=1\); otherwise \(2\) | \(1\) if \(n=1\); otherwise \(2\) | \(n=1:\ 0\); \(n=2:\) all \(1\); \(n\ge3:\) two \(1\)'s and \(n-2\) \(2\)'s |
| \(C_n\), \(n\) even | \(n/2\) | \(2\) | \(2\) | All \(2\) |
| \(C_n\), \(n\) odd | \(\lfloor n/2\rfloor\) | \(3\) if \(n=3\); otherwise \(2\) | \(3\) | All \(2\) |
| \(K_{a,b}\) | \(\max(a,b)\) | \(2\) | \(2\) | Vertices in \(A\) have degree \(b\); vertices in \(B\) have degree \(a\) |
For each graph, the average degree also follows from its size: every edge contributes one to the degree of each endpoint, so the sum of the degrees is twice the number of edges. Thus \(\bar d(P_n)=2(n-1)/n\), \(\bar d(C_n)=2\), and \(\bar d(K_{a,b})=2ab/(a+b)\). The derivations below justify the parameter formulas, including their boundary and parity cases.
Why the Formulas Hold
Proof. First consider \(P_n\). Partition its vertices into consecutive pairs \(\{1,2\},\{3,4\},\dots\), with a final singleton if \(n\) is odd. Each pair contains an edge, so an independent set contains at most one vertex from each pair and at most one from the final singleton. This gives an upper bound of \(\lceil n/2\rceil\). The vertices with odd labels form an independent set: any two distinct odd labels differ by at least \(2\), so they are not joined by a path edge. There are \(\lceil n/2\rceil\) such vertices. Therefore \(\alpha(P_n)=\lceil n/2\rceil\).
For \(n=1\), the only clique has size \(1\), and one color suffices. For \(n\ge2\), an edge is a clique of size \(2\), while there is no clique of size \(3\): in a path, the two neighbors of any vertex are not adjacent to each other. Thus \(\omega(P_n)=2\). Coloring odd labels with one color and even labels with another is proper, and an edge requires two different colors, so \(\chi(P_n)=2\). The endpoint degrees are \(1\) when \(n\ge2\); every internal vertex, if there is one, has degree \(2\). For \(n=1\), its sole vertex has degree \(0\). These facts give all the path degree cases.
Now consider \(C_n\). If an independent set contains \(k\) vertices, each selected vertex has a successor around the cycle, and that successor is unselected. Distinct selected vertices have distinct successors. Therefore there are at least \(k\) unselected vertices, so \(k\le n-k\), or \(k\le\lfloor n/2\rfloor\). To attain this bound when \(n=2k\), choose \(1,3,\dots,2k-1\). When \(n=2k+1\), choose \(1,3,\dots,2k-1\), which is \(1,3,\dots,n-2\). In either case, no two chosen vertices are consecutive around the cycle: in the odd case, in particular, neither \(n\) nor \(n-1\) is chosen, so the closing edge \(n1\) causes no conflict. The chosen set has \(\lfloor n/2\rfloor\) vertices. Hence \(\alpha(C_n)=\lfloor n/2\rfloor\).
For \(C_3\), all three vertices form a clique. For \(n\ge4\), the two neighbors of any vertex are not adjacent, so a clique cannot contain three vertices. Since every cycle has edges, \(\omega(C_n)=2\) for \(n\ge4\). To color a cycle with two colors, adjacent vertices must alternate colors as one moves around it. The last edge returns to the first vertex, and the alternating pattern agrees across that edge exactly when \(n\) is even. Thus an even cycle has chromatic number \(2\), while an odd cycle cannot be colored with two colors. An odd cycle can be colored with three: alternate two colors on vertices \(1,\dots,n-1\), and give vertex \(n\) a third color. Since \(n-1\) is even, vertices \(1\) and \(n-1\) have different colors; the third color at \(n\) therefore differs from both neighbors \(1\) and \(n-1\). This proves that \(\chi(C_n)=3\) for odd \(n\). Every cycle vertex has two distinct neighbors, so every degree is \(2\).
Finally, consider \(K_{a,b}\) with parts \(A\) and \(B\). An independent set cannot contain a vertex from each part, because every such pair is adjacent. It can contain all vertices of either part, so its largest possible size is \(\max(a,b)\). A clique has at most one vertex from each part, and an edge gives a clique of size \(2\); hence \(\omega(K_{a,b})=2\). Coloring one part with one color and the other part with a second gives a proper coloring, and an edge shows that one color cannot suffice. Thus \(\chi(K_{a,b})=2\). Each vertex in \(A\) is adjacent to all \(b\) vertices in \(B\), and each vertex in \(B\) to all \(a\) vertices in \(A\). Consequently \(\delta(K_{a,b})=\min(a,b)\) and \(\Delta(K_{a,b})=\max(a,b)\).
For the average-degree formulas, \(P_n\) has \(n-1\) edges, \(C_n\) has \(n\) edges, and \(K_{a,b}\) has \(ab\) edges. Counting each edge once at each endpoint gives degree sums \(2(n-1)\), \(2n\), and \(2ab\), respectively. Dividing by the vertex counts \(n,n,a+b\) gives the stated averages. \(\square\)
Worked Calculations
Worked Example: Independence and Degrees in a Path
Let \(G=P_7\), with \(V(G)=\{1,2,3,4,5,6,7\}\) and \(E(G)=\{12,23,34,45,56,67\}\). We calculate all four parameters.
The formula gives \(\alpha(G)=\lceil7/2\rceil=4\). The set \(\{1,3,5,7\}\) is independent, because none of its labels are consecutive, and it has four vertices. The pairs \(\{1,2\},\{3,4\},\{5,6\}\), together with the singleton \(\{7\}\), show that no independent set can have more than four vertices.
Since \(7\ge2\), \(\omega(G)=2\), witnessed by the edge \(12\); there is no triangle in a path. The odd-labelled vertices \(\{1,3,5,7\}\) and even-labelled vertices \(\{2,4,6\}\) give a proper two-coloring, and the edge \(12\) requires at least two colors. Thus \(\chi(G)=2\).
The degrees in vertex order are \(1,2,2,2,2,2,1\). Their sum is \(1+2+2+2+2+2+1=12\), so \(\delta(G)=1\), \(\Delta(G)=2\), and \(\bar d(G)=12/7\). Check: there are \(6\) edges, so \(2|E(G)|/|V(G)|=2\cdot6/7=12/7\), agreeing with the degree sum.
Worked Example: The Parity Effect in a Cycle
Let \(G=C_7\), with \(V(G)=\{1,2,3,4,5,6,7\}\) and \(E(G)=\{12,23,34,45,56,67,71\}\). The independence number is \(\lfloor7/2\rfloor=3\). One independent set of that size is \(\{1,3,5\}\): the cycle edges incident with these vertices go to \(2,7\), \(2,4\), and \(4,6\), respectively, so none joins two selected vertices. The successor argument in the proof gives the upper bound \(3\).
The graph has no triangle because \(7\ge4\), and it has edges, so \(\omega(G)=2\). It is not two-colorable: starting at vertex \(1\), a two-coloring would alternate around the cycle, giving vertex \(7\) the same color as vertex \(1\); the edge \(71\) forbids that. The three-color construction in the proof gives \(\chi(G)=3\). Each of the seven vertices has degree \(2\), so \(\delta(G)=\Delta(G)=2\) and \(\bar d(G)=2\).
Check: the degree sum is \(7\cdot2=14\), while twice the edge count is \(2\cdot7=14\). Also, the set \(\{1,3,5\}\) has the predicted size \(3\), not \(4\); including vertex \(7\) as well would fail because \(71\) is an edge.
Worked Example: A Complete Bipartite Graph
Let \(G=K_{2,4}\), with parts \(A=\{a_1,a_2\}\) and \(B=\{b_1,b_2,b_3,b_4\}\), and edge set \(E(G)=\{a_i b_j: 1\le i\le2,\ 1\le j\le4\}\). Explicitly, these are \(a_1b_1,a_1b_2,a_1b_3,a_1b_4,a_2b_1,a_2b_2,a_2b_3,a_2b_4\).
An independent set can be all of \(A\), of size \(2\), or all of \(B\), of size \(4\), but cannot contain vertices from both parts. Thus \(\alpha(G)=\max(2,4)=4\). Every clique has at most one vertex from each part, while \(a_1b_1\) is an edge, so \(\omega(G)=2\). The two parts themselves provide a proper two-coloring, and the edge \(a_1b_1\) prevents a one-coloring; hence \(\chi(G)=2\).
Each of \(a_1,a_2\) has degree \(4\), and each of \(b_1,b_2,b_3,b_4\) has degree \(2\). Therefore \(\delta(G)=2\), \(\Delta(G)=4\), and the degree sum is \(2\cdot4+4\cdot2=16\). The edge set has \(8\) edges, so the average degree is \(16/6=8/3\). Check: the formula \(2ab/(a+b)\) gives \(2\cdot2\cdot4/(2+4)=16/6=8/3\), as computed directly.
Common Pitfalls
Forgetting the closing edge of an odd cycle. A tempting but incorrect claim is that the odd-labelled vertices of every cycle form an independent set of size \(\lceil n/2\rceil\). In \(C_7\), that would select \(\{1,3,5,7\}\), but \(7\) is adjacent to \(1\) through the edge \(71\). The corrected set for an odd cycle \(C_n\) is \(1,3,\dots,n-2\), which has \(\lfloor n/2\rfloor\) vertices. On an even cycle \(C_n\), the set \(1,3,\dots,n-1\) has \(n/2\) vertices and does not include both ends of the closing edge.
Confusing the parameter formulas across families. For paths, \(\alpha(P_n)=\lceil n/2\rceil\), while for cycles, \(\alpha(C_n)=\lfloor n/2\rfloor\). The difference is caused by the extra closing edge in a cycle. Likewise, every cycle vertex has degree \(2\), but a path has endpoints of degree \(1\) when \(n\ge2\). Finally, \(C_3\) is an exceptional clique: it has \(\omega(C_3)=3\), unlike longer cycles.
These calculations are useful as benchmarks: they make it possible to check a proposed general bound against familiar graph families. The parity cases also show why a formula should be verified against the actual edge set, rather than inferred from a pattern that overlooks one edge.
Check Your Understanding
For each question, use the definitions and formulas above; when testing a set, check every edge, including any closing edge of a cycle.
- Find \(\alpha(P_8)\), \(\omega(P_8)\), \(\chi(P_8)\), \(\delta(P_8)\), and \(\Delta(P_8)\).
- Give an independent set of maximum size in \(C_9\), and explain why no larger independent set is possible.
- Determine \(\omega(C_3)\) and \(\chi(C_3)\). What makes this cycle different from \(C_5\)?
- For \(K_{3,5}\), find \(\alpha\), \(\omega\), \(\chi\), the degrees in each part, and the average degree.
- Explain why the odd-labelled vertices of \(C_7\) are not an independent set, and give a corrected maximum independent set.