Counting Crossings Across Subgraphs
A drawing of a graph can have many crossings, but a particular crossing may appear in the drawings of several subgraphs. Counting how many subgraphs contain each crossing gives a way to use a known crossing number as a lower bound for a larger graph. The key is to count the same quantity in two ways: first by summing the crossings inside each copy of a fixed graph, and then by summing over the crossings of the whole graph.
All graphs in this tutorial are finite and simple. A drawing places distinct vertices in the plane and represents each edge by a curve joining its endpoints. We use a good drawing: no edge passes through a vertex other than its endpoints, crossings are transverse, no three edges cross at one interior point, edges with a common endpoint do not cross, and any two edges cross at most once. The standard normalization for crossing number allows a crossing-minimal drawing to be chosen good; this is part of the earlier material on general-position drawings. Thus crossings can be counted as pairs of edges.
Fix a graph \(H\) and let \(\mathcal{H}\) be a specified family of copies of \(H\) in \(G\). Write \(N=|\mathcal{H}|\). For two independent edges \(e,f\) of \(G\), their copy multiplicity is the number of members of \(\mathcal{H}\) that contain both edges. Let \(M\) be the maximum of these multiplicities over all independent edge pairs in \(G\). If \(G\) has no independent edge pair, define \(M=0\). This convention makes \(M\) defined even in small or sparse graphs. When there is at least one independent pair, the maximum is taken over a finite nonempty set.
The Subgraph-Counting Bound
Proof. Choose a good drawing \(D\) of \(G\) with exactly \(\operatorname{cr}(G)\) crossings. For each copy \(H_i\in\mathcal{H}\), retain just the vertices and edges of that copy. The resulting drawing is a drawing of \(H\), so it has at least \(\operatorname{cr}(H)\) crossings. Summing over all \(N\) copies, the total number of crossing occurrences in these restricted drawings is at least \(N\operatorname{cr}(H)\).
Now count the same occurrences by crossings of \(D\). Each crossing of \(D\) is between independent edges, and because \(D\) is good, a fixed pair of edges crosses at most once. A crossing between \(e\) and \(f\) appears in exactly as many restricted drawings as there are copies containing both \(e\) and \(f\), which is at most \(M\). There are \(\operatorname{cr}(G)\) crossings in \(D\), so the total number of occurrences is at most \(M\operatorname{cr}(G)\). Comparing the lower and upper counts proves the inequality. If \(M>0\), division by \(M\) gives the stated lower bound. If \(M=0\), there are no independent edge pairs and hence no crossings in a good drawing; the inequality still holds because its right side is zero and each restricted drawing has zero crossings. \(\square\)
The inequality counts copies with their multiplicities; it does not assume that crossings in different copies are distinct. In fact, controlling how often one crossing is counted is precisely the purpose of \(M\). A lower bound need not be an integer as written. Since \(\operatorname{cr}(G)\) is an integer, any real lower bound can be rounded up to the next integer.
Complete Graphs: Counting Copies of \(K_5\)
The exact crossing number \(\operatorname{cr}(K_5)=1\) was established in the earlier material on exact crossing numbers. We use that value here. In \(K_n\), take as \(\mathcal{H}\) all subgraphs induced by five-vertex subsets; each is a copy of \(K_5\). When \(n\ge5\), their number is \(\binom{n}{5}\). Any independent pair of edges has four distinct endpoints. A \(K_5\) copy containing that pair is obtained by choosing its fifth vertex from the remaining \(n-4\) vertices, so every independent pair has multiplicity \(n-4\).
Proof. There are \(N=\binom{n}{5}\) copies, each with crossing number \(1\), and the maximum multiplicity is \(M=n-4>0\). Substitution in the theorem gives \(\operatorname{cr}(K_n)\ge\binom{n}{5}/(n-4)\). Expanding \(\binom{n}{5}=n(n-1)(n-2)(n-3)(n-4)/120\) and cancelling \(n-4\) gives the displayed expression. \(\square\)
Worked Example: A Lower Bound for \(K_6\)
There are \(\binom{6}{5}=6\) copies of \(K_5\) in \(K_6\). Fix any independent pair of edges. Its four endpoints leave \(6-4=2\) vertices available for the fifth vertex of a \(K_5\), so its multiplicity is \(M=2\). Using \(\operatorname{cr}(K_5)=1\), the bound is $$ \operatorname{cr}(K_6)\ge\frac{6\cdot1}{2}=3. $$
Check: In \(K_6\), independent edge pairs can be counted by choosing four endpoints and one of the three pairings of those endpoints, giving \(\binom{6}{4}\cdot3=15\cdot3=45\). Each \(K_5\) contains \(\binom{5}{4}\cdot3=5\cdot3=15\) independent edge pairs, so the six copies account for \(6\cdot15=90\) incidences. The average multiplicity is \(90/45=2\), agreeing with the direct count for a fixed pair. The lower bound is an integer and requires no further rounding.
Complete Bipartite Graphs: Counting Copies of \(K_{3,3}\)
The exact crossing number \(\operatorname{cr}(K_{3,3})=1\) is also available from the earlier material on exact crossing numbers. In \(K_{m,n}\), its two vertex parts have sizes \(m\) and \(n\), and every edge joins a vertex in one part to a vertex in the other. For \(m,n\ge3\), choose three vertices from each part to obtain a copy of \(K_{3,3}\). Hence the number of copies in this family is \(\binom{m}{3}\binom{n}{3}\).
Any independent pair of edges uses two distinct vertices from each part. To complete those four endpoints to a \(K_{3,3}\), choose one additional vertex from the first part and one from the second. Thus each independent pair lies in exactly \((m-2)(n-2)\) copies. Applying the counting theorem gives the following bound.
Proof. The family has \(N=\binom{m}{3}\binom{n}{3}\) copies, each with crossing number \(1\), and each independent edge pair has multiplicity \(M=(m-2)(n-2)>0\). The theorem gives the first expression. Using \(\binom{m}{3}=m(m-1)(m-2)/6\) and \(\binom{n}{3}=n(n-1)(n-2)/6\), their product divided by \((m-2)(n-2)\) is \(mn(m-1)(n-1)/36\). \(\square\)
Worked Example: The Bound for \(K_{3,4}\)
There are \(\binom{3}{3}\binom{4}{3}=1\cdot4=4\) copies of \(K_{3,3}\). For a fixed independent edge pair, the two parts have one and two unused vertices, respectively, so it lies in \(M=(3-2)(4-2)=1\cdot2=2\) copies. Therefore $$ \operatorname{cr}(K_{3,4})\ge\frac{4\cdot1}{2}=2. $$
Check: Count independent edge pairs in the host by choosing two of the three vertices in the first part, two of the four in the second, and one of the two pairings between the chosen pairs. This gives \(\binom{3}{2}\binom{4}{2}\cdot2=3\cdot6\cdot2=36\) pairs. Each \(K_{3,3}\) contains \(\binom{3}{2}\binom{3}{2}\cdot2=3\cdot3\cdot2=18\) such pairs. Across the four copies there are \(4\cdot18=72\) incidences, and \(72/36=2\), confirming the multiplicity.
Worked Example: Rounding the Bound for \(K_{4,5}\)
The number of \(K_{3,3}\) copies is \(\binom{4}{3}\binom{5}{3}=4\cdot10=40\). For a fixed independent edge pair, choose one additional vertex from the first part and two from the second, giving multiplicity $$ M=(4-2)(5-2)=2\cdot3=6. $$ Thus $$ \operatorname{cr}(K_{4,5})\ge\frac{40\cdot1}{6}=\frac{20}{3}. $$ Because the crossing number is an integer, this implies \(\operatorname{cr}(K_{4,5})\ge7\).
Check: The host has \(\binom{4}{2}\binom{5}{2}\cdot2=6\cdot10\cdot2=120\) independent edge pairs. A \(K_{3,3}\) contains \(\binom{3}{2}\binom{3}{2}\cdot2=18\), so the 40 copies produce \(40\cdot18=720\) incidences. Dividing gives \(720/120=6\), the same multiplicity as the direct choice of extra vertices.
What the Bound Does—and Does Not—Count
The method is useful when a graph contains many copies of a smaller graph whose crossing number is known, and when each pair of independent edges is contained in relatively few of those copies. The numerator measures how much crossing is forced across all the copies; the denominator limits how often any one crossing can pay toward that total. Copies can overlap substantially, so simply multiplying their number by \(\operatorname{cr}(H)\) would overcount unless this multiplicity is controlled.
The result is a lower bound, not automatically an exact answer. It does not construct a drawing attaining the bound, and the multiplicity maximum can make the bound weaker than a more refined count. Nor does the argument require that the copies be induced: it only uses their edges and the crossing number of the graph they form. The examples use induced copies because they are easy to count in complete and complete bipartite graphs.
Common mistake: confusing total pairs with multiplicity. In \(K_{3,4}\), there are 36 independent edge pairs in the whole graph. It would be wrong to set \(M=36\): \(M\) is the number of selected \(K_{3,3}\) copies containing one fixed pair, not the total number of pairs in the host. For a fixed pair, there are two choices to complete its vertices to a \(K_{3,3}\), so \(M=2\). Using the total pair count would give the incorrect estimate \(4/36\), rather than the valid bound \(4/2=2\).
A second point to check is whether the family is empty or whether there are independent edge pairs. The formulas for complete and complete bipartite graphs above assume \(n\ge5\) and \(m,n\ge3\), respectively, so their copy families are nonempty and \(M>0\). In other settings, the convention \(M=0\) handles the absence of independent pairs, but division by \(M\) is not permitted. The undivided inequality remains the general statement.
Check Your Understanding
For each question, identify the copy family and the multiplicity being counted before applying the bound.
- In \(K_7\), how many \(K_5\) copies are there, and how many contain a fixed independent edge pair? What lower bound follows?
- For \(K_{5,6}\), determine the number of \(K_{3,3}\) copies and the multiplicity of a fixed independent edge pair.
- Explain why crossings in a good drawing are associated only with independent edge pairs.
- In the \(K_{4,5}\) example, why must the real lower bound \(20/3\) be rounded up rather than down?
- State what the convention \(M=0\) means and why the divided form of the bound cannot be used when \(M=0\).