Incidence Bounds on Edge Partitions of $K_{n}$

Several characterizations of edge-connectivity are known within the literature. See, for instance, [5], [3], or [6]. In recent years there has been a push to understand an analogous notion of connectivity for nodes [2]. One earlier result within this area is found in [4].

Here $|N_{G}(S)|$ is, of course, the number of nodes in $G$ adjacent to $S$. This theorem is then used to prove the following within the same paper.

In an effort to extend this to a larger family of strongly regular graphs the Johnson $J(n,2)$ (the line graph of $K_{n}$) was considered. It was remarked that this problem is equivalent to proving the main theorem within this work. Since then, the analogue for theorem 1 on $J(n,2)$ was proven in [1] but the incidence bound remained an open question.

In this paper we provide an alternate proof to the one found in [1] of the parallel result for the line graph of the connected graph $K_{n}$. In doing so we prove certain incidence bounds for edge partitions of $K_{n}$.

The author would like to thank Joseph Cheriyan for his comments and encouragements. Without him this paper would not have been possible.

Let $K_{n}$ be the connected graph on $n$ vertices. Partition the edges of $K_{n}$ into $3$ sets $S$,$T$, and $Z$ with $|Z|=n-3$. We prove that the incidence of $S$ and $T$ is at least the minimum of the incidence of either $Z$ and $T$ or $Z$ and $S$.

Label the vertices $v_{1},\ldots,v_{n}$ and let the degree in $S,T,Z$ of $v_{i}$ be $s_{i},t_{i},z_{i}$, respectfully. We prove

We begin with an elementary observation, since the degree of each node is $n-1$,it follows that $s_{i}+t_{i}+z_{i}=n-1$. Suppose $s_{1},\ldots,s_{p}$ are the nodes with degree in $S$ equal to $0$, let $t_{p+1},,\ldots,t_{p+q}$ be the nodes with degree in $T$ being $0$. We let $P=\{v_{1},\ldots,v_{p}\}$, $Q=\{v_{p+1},\ldots v_{p+q}\}$, $R=V\setminus(P\cup Q)$.

Assume for contradiction that $\sum_{i=1}^{n}s_{i}t_{i}<\sum_{i=1}^{n}z_{i}t_{i}$ and $\sum_{i=1}^{n}s_{i}t_{i}<\sum_{i=1}^{n}z_{i}s_{i}$. We first prove a few quick lemmas:

Now for $p+q\leq 2$, using 1 and 3

Contradiction.

We can WLOG assume $p\geq q$. Assume $p\geq 4$. Then by summing the first two lines of 1

Rearranging and simplifying terms now gives us:

The goal is to prove the RHS is larger than the LHS for contradiction. Notice:

The last $(n+1)q$ is from at least $z_{i}=1$ for all $i\in Q$, otherwise $z_{i}=0$ implies there is some vertex with all edges in $S$ meaning $p=0$. And bounding $2(n-1)-z_{i}\geq n+1$.

Substituting the above in and collecting $n$ yields

We assumed that $p$ is at least $4$. The worst case for the above is when $q=p$ with the largest zero of the RHS occurring at

Recall the bound $p+q<2\sqrt{n-3}$. This gives $\left(\frac{p}{2}\right)^{2}+3<n$. Substitute this for $n$ in the above. What one obtains is a polynomial that is positive for all $p\geq 4$. Our contradictive assumption was that this expression is negative, contradiction.

We have only a few cases left to consider: $(p,q)\in\{(2,1),(2,2),(3,0),(3,1),(3,2),(3,3)\}$. One can verify by computer that the conjecture is true for $n\leq 15$ for the given $(p,q)$. For larger $n$ we use the following technique.

By symmetry we can assume that $p\geq q$ and that $p$ is at least $2$. Consider the $2$ vertices, $v_{1},v_{2}$ in $P$. Let $P_{2}$ be the subset of vertices in $R$ connected to both $v_{1}$ and $v_{2}$ via an edge in $T$. Use $\sigma$ to denote $|P_{2}|$. We must then have $z_{1}+z_{2}=2(n-1)-t_{1}-t_{2}$ by degree considerations on $P$. Also, $\sigma\geq t_{1}+t_{2}-2p+3-(n-q-p-2)=t_{1}+t_{2}-p+q-n+5$ by pigeonhole principle. This comes from the realization that in the worst case we have $t_{1}+t_{2}-2p+3$ ($-2p+3$ comes from edges contained in $P$) for the case where edges going to the $n-p-q-2$ vertices in $R$. A double count occurs at least $t_{1}+t_{2}-2p+3-(n-q-p-2)$ many times.

We intend to show

Indeed

Where $C_{z}:=\frac{1}{2}\sum_{i=1}^{n}z_{i}^{2}-\sum_{R}z_{i}-\sum_{P_{2}}z_{i}$. Comparing the above to $(n-1)(n-3)$ gives a difference of

That is, we wish to show

for a contradiction.

The penultimate step is using this easy bound on $C_{z}$

We can finally simplify the fraction on (6) to

by finding common denominators and reducing.

So we are left with $n>\frac{1}{2}n+\frac{15}{2}$, the theorem is true for $n>15$, as required.

To summarize, we are left with

We now demonstrate that the bound obtained on the incidence is in some sense the best possible. Suppose we strengthened the condition on the size of $Z$ to be $n-2$ instead of $n-3$. In this case we can construct a family of counterexamples.

Let $n>5$ and consider the edge partition

The incidence of $S$ and $T$ is then $2(n-3)$ while the incidence of $S$ and $Z$ is $2(n-3)+2$. The incidence between $T$ and $Z$ is at least $(n-3)(n-1)$. Therefore, the bound from 4 fails.

We’ve added an illustration of the case $n=5$ below.

The blue edges are in $S$, the black, $T$, and red, $Z$.

Recall theorem 1. Following the logic of the proof as in [4] we see that

implies, for $k=n-2$,

where $\hat{S},\hat{Z}$ are induced vertex subsets of $J(n,2)$ coming from edges in $K_{n}$ after taking the line graph. As a consequence of the incidence bounds,