<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\usepackage{longtable}
\makeatletter
\def\dual#1{\expandafter\dual@aux#1\@nil}
\def\dual@aux#1/#2\@nil{\begin{tabular}{@{}c@{}}#1\\#2\end{tabular}}
\makeatother

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Integer Sequences from Configurations \\
in the Hausdorff Metric Geometry \\
\vskip .09in
via Edge Covers of Bipartite Graphs
}
\vskip 1cm

\begin{minipage}{2.8in}
\begin{center}
Steven Schlicker\\
Grand Valley State University\\
Department of Mathematics\\
1 Campus Drive\\
Allendale, MI 49401\\
USA\\
\href{mailto:schlicks@gvsu.edu}{\tt schlicks@gvsu.edu}
\end{center}
\end{minipage}
\quad 
\begin{minipage}{3.3in}
\begin{center}
Roman Vasquez\\
Auburn University\\
Department of Mathematics and Statistics\\
221 Parker Hall\\
Auburn, AL 36849\\
USA\\
\href{mailto:roman.vasquez@auburn.edu}{\tt roman.vasquez@auburn.edu}
\end{center}
\end{minipage}
\ \\
\vskip .2in
Rachel Wofford\\
Pacific Northwest National Laboratory\\
1100 Dexter Ave N.\\
Seattle, WA 98109\\
USA\\
\href{mailto:re.wofford@pnnl.gov}{\tt re.wofford@pnnl.gov}
\end{center}

\vskip .2 in


\begin{abstract} The Hausdorff metric provides a way to measure the
distance between nonempty compact sets in $\mathbb{R}^N$, from which we
can build a geometry of sets. This geometry is very different than the
standard Euclidean geometry and provides many interesting results. In
this paper we focus on line segments in this geometry, where pairs
of disjoint sets $A$ and $B$ satisfying certain distance conditions
have the property that there are exactly $m$ different sets on the
line segment $\overline{AB}$ at every distance from $A$, where $m$ can
assume many values different than one. We provide new families of sets
that generate previously unrecorded integer sequences via these values
of $m$ by connecting the values of $m$ to the number of edge coverings
of a graph corresponding to the sets $A$ and $B$.
\end{abstract}

\section{Introduction}


The Hausdorff metric $h$ imposes a geometry on the hyperspace $\mathcal{H}(\mathbb{R}^N)$ of all nonempty compact subsets of $\mathbb{R}^N$. One notion of betweenness in this geometry is an extension of betweenness in Euclidean geometry. For certain positive integers $m$, there exists a pair of disjoint finite sets $A$ and $B$ for which there are $m = \#([A,B])$ different sets on the line segment defined by these sets at every distance from one of the sets. There are many fascinating and interesting properties of these numbers $m = \#([A,B])$. For example, for each integer $m$ between $1$ and $18$ there exist sets $A$ and $B$ such that $\#([A,B]) = m$, but no such sets exist for $m = 19$. Further discussion of this can be found in Section~\ref{section:betweeness}.

The number $\#([A,B])$ is related to edge covers of bipartite graphs, which is explained in more detail in Section~\ref{section:graphs}. For each fixed value of $m$, varying the size of one of the partite sets yields different numbers of edge covers, generating integer sequences. These sequences help us understand more about line segments in $\mathcal{H}(\mathbb{R}^N)$ and edge covers of graphs. 


\section{The Hausdorff metric}

Felix Hausdorff introduced the Hausdorff metric $h$ in the early 20th century as a way to measure the distance between compact sets. The Hausdorff metric imposes a geometry on the space $\mathcal{H}(\mathbb{R}^N)$, which is the subject of our study. Throughout, we let $d_E$ denote the standard Euclidean metric in $\mathbb{R}^N$. 

\begin{definition}  \label{def:Hausdorff} The \emph{Hausdorff distance} $h$ between sets $A$ and $B$ in $\mathcal{H}(\mathbb{R}^N)$ is
\[h(A,B)=\max\{d(A,B),d(B,A)\},\]
where 
\[d(A,B)=\max_{a \in A} \{d(a,B)\}\]
and 
\[d(x,A)=\min_{a \in A} \{d_E(x,a)\}\]
for every $x \in A$.  
\end{definition}

In other words, to find the distance $d(A,B)$ from set $A$ to set $B$, we measure the Euclidean distance from a point $x$ in $A$ farthest from $B$ to a point in $B$ closest to $x$. The Hausdorff distance between $A$ and $B$ is then the larger of $d(A,B)$ and $d(B,A)$. The mapping $h$ in Definition \ref{def:Hausdorff} is called the \emph{Hausdorff metric}. The proof that $h$ is a metric can be found in many topology texts, see Barnsley or Edgar \cite{Barnsley, Edgar}, for example.

\begin{example} \label{ex:two_lines}
Let $a_1 = (-2,0)$, $a_2 = (-1,0)$, $b_1 = (1,-1)$, and $b_2 = (1,1)$ in $\mathbb{R}^2$, and define segments $A$ and $B$ in $\mathbb{R}^2$ as $A = \overline{a_1a_2}$ and $B = \overline{b_1b_2}$ as shown at left in Figure \ref{fig:Segment_Example}.
\begin{figure}[!ht]
\begin{center}
\resizebox{!}{2.0in}{\includegraphics{Segment_Example.eps}} \hspace{0.5in} \resizebox{!}{2.0in}{\includegraphics{Segment_Example_Dilation.eps}}
  \caption{Left: Segments $A$ and $B$. \ Right: Dilations of the segments.}
  \label{fig:Segment_Example}
\end{center}
\end{figure}
In this example, $d(A,B) = d_E(a_1,(1,0)) = 3$ and $d(B,A) = d_E(b_1,a_2) = \sqrt{5}$. So $h(A,B) = 3$. (Note that $d$ itself is not a metric since $d$ is not symmetric.) 
\end{example}

\section{Betweenness and finite configurations} 
\label{section:betweeness}

We can use the Hausdorff metric to extend the notion of Euclidean betweenness to $\mathcal{H}(\mathbb{R}^N)$.  
 
\begin{definition} Let $A$, $B$, and $C$ be in $\mathcal{H}(\mathbb{R}^N)$. The set $C$ is \emph{between} $A$ and $B$ in $\mathcal{H}(\mathbb{R}^N)$ if  
\[h(A,B) = h(A,C) + h(C,B).\]
\end{definition}

We adopt the notation $ACB$ from Blumenthal \cite{Blumenthal} when $C$ is between $A$ and $B$. So, as in Euclidean geometry, the line segment determined by $A \neq B$ in $\mathcal{H}(\mathbb{R}^N)$ is the set of all sets $C$ satisfying $ACB$. 

The Hausdorff metric is a complicated one, and it is generally not clear how to determine which sets lie on a given line segment. One construction that helps in this regard is the dilation of a set. 

\begin{definition} Let $A$ be in $\mathcal{H}(\mathbb{R}^N)$ and let $s$ be a positive real number. The \emph{dilation} of $A$ by $s$ is the set 
\[(A)_s=\{x \in \mathbb{R}^N \mid d_E(x,a) \leq s \mbox{ for some } a \in A\}.\]
\end{definition}

\begin{example} Consider again the segments $A$ and $B$ presented in Example \ref{ex:two_lines}. In this case, we have $r = h(A,B) = 3$. Let $s$ be a real number between $0$ and $3$ and let $t = r-s$. See Figure \ref{fig:Segment_Example} at right for illustrations of the dilations $(A)_s$ and $(B)_t$ for a fixed value of $s$.
 \end{example}

The dilation of a set $A$ by $s$ has two important properties. The first is that $h(A,(A)_s) = s$. The second is that if $C$ satisfies $ACB$, then $C \subseteq (A)_s \iff d(C,A) \leq s$ \cite[Theorem 4]{BMMS}. It follows that $C$ satisfies $ACB$ with $h(A,C) = s$, then $C$ is a subset of $(A)_s \cap (B)_{h(A,B) - s}$. An example of this intersection is shown at right in Figure \ref{fig:Segment_Example}. In fact, Bogdewicz \cite{Bog} shows that the set $C_s = (A)_s \cap (B)_{h(A,B) - s}$ always satisfies $AC_sB$ with $h(A,C_s) = s$. 

Given sets $A$ and $B$ in $\mathcal{H}(\mathbb{R}^N)$, there are two possibilities for sets $C$ that satisfy $ACB$. Blackburn et al.\ \cite{BLSSZ} show that if there is a point $a \in A$ or a point $b \in B$ such that $d(a,B) \neq h(A,B)$ or $d(b,A) \neq h(A,B)$, then there are infinitely many different sets $C$ that satisfy $ACB$ and $d(A,C) = s$ for any $0 &lt; s &lt; h(A,B)$. The other possibility is the one of interest in this paper and we call such a pair of sets a \emph{configuration}.  

\begin{definition}
\label{def:configuration}
A \emph{configuration} is a pair $A,B$ of sets in $\mathcal{H}(\mathbb{R}^N)$ such that $d(a,B) = d(b,A) = h(A,B)$ for every $a \in A$ and $b \in B$. 
\end{definition}

We will denote the configuration pair $A$, $B$ as $[A,B]$. Blackburn et al.\ \cite{BLSSZ} demonstrate that if $A$ and $B$ are finite sets such that $[A,B]$ is a finite configuration, then there is a finite number $k$ such that there are exactly $k$ sets $C$ satisfying $ACB$ with $h(A,C) = s$ for every $0 &lt; s &lt; h(A,B)$. We denote this number $k$ of sets $C$ satisfying $ACB$ for a finite configuration $[A,B]$ -- that is, the number of different sets which exist at the same location on the line segment between $A$ and $B$ in $\mathcal{H}(\mathbb{R}^N)$ -- by $\#([A,B])$. Moreover, the number of sets $C$ with $ACB$ and $h(A,C) = s$ is the same for every value of $s$. Lund et al.\ \cite{LSS} show that there are infinitely many different integers that appear as $\#([A,B])$ -- all of the Fibonacci numbers and even indexed Lucas numbers, for example. Every integer between $1$ and $18$ is $\#([A,B])$ for some $[A,B]$, and every number between $20$ and $36$ is $\#([A,B])$ for some $[A,B]$. However, Blackburn et al.\ \cite{BLSSZ} show that there is, surprisingly, no configuration $[A,B]$ with $\#([A,B]) = 19$, and Honigs \cite{Honigs} proves that there is no configuration $[A,B]$ with $\#([A,B]) = 37$. Ovsyannikov \cite{Ovsyannikov} extends these results to show that there exist no configurations $[A,B]$ with $\#([A,B])$ equal to 41, 59, or 67. 

\section{Bipartite graphs}
\label{section:graphs}

We are interested in determining which integers can occur as $\#([A,B])$ for some finite configuration $[A,B]$. As we will see, there is a correspondence between finite configurations and bipartite graphs, and $\#([A,B])$ is equal to the number of edge covers of the corresponding graph. 


We use the standard terminology and notation from graph theory. We consider simple graphs $G = (V,E)$ where $V$ is the vertex set and $E$ is the edge set. We say that two vertices are adjacent if they have an edge in common, two edges are incident if they share a vertex, and an edge and a vertex are incident if the edge contains the vertex. A bipartite graph is a graph $G = (V,E)$ such that there exist disjoint sets $V_1$ and $V_2$ (called parts) such that $V = V_1 \cup V_2$ and there are no adjacent vertices within a part.

Now we make the connection between finite configurations and bipartite graphs. Given $A$ and $B$ in $\mathcal{H}(\mathbb{R}^N)$, any set $C$ that lies on the line segment $\overline{AB}$ must satisfy $h(A,C)=s$ and $h(C,B)=h(A,B)-s$ for some $0&lt;s&lt;h(A,B)$. This implies that $C \subseteq (A)_{s} \cap (B)_{h(a,b)-s}$. If $[A,B]$ is a finite configuration, then $(A)_{s} \cap (B)_{h(A,B)-s}$ is a finite set as illustrated at left in Figure \ref{fig:DilationIntersection}, where $A=\{a_{1},a_{2}\}$, $B=\{b_{1},b_{2}\}$, and $C = \{c_1, c_2, c_3, c_4\}$.

\begin{figure}[!ht]
\begin{center}
  \resizebox{!}{2.0in}{\includegraphics{Configuration_Graph.eps}} 
 \caption{Left: Sets on the line segment $\overline{AB}$ in $\mathcal{H}(\mathbb{R}^N)$. Right: A corresponding bipartite graph.}
  \label{fig:DilationIntersection}
\end{center}
\end{figure}

We can represent this configuration as a bipartite graph. If $[A,B]$ is a finite configuration, let $V=A \cup B$, and let $E$ be the set $\{(a,b): a \in A \text{ and } b \in B \text{ such that } d_{E}(a,b)=h(A,B)\}$. Then $G_{[A,B]}=(V,E)$ forms a bipartite graph with parts $A$ and $B$ and edge set $E$. Notice that if $C$ satisfies $ACB$ with $h(A,C) = s$, then each point $c \in C$ satisfies $a_{c}cb_{c}$ for some $a_{c} \in A$ and $b_{c} \in B$, with $d_{E}(a_{c},c)=s$. This point $c$ can be identified with the edge $(a_{c},b_{c})$ in $G_{[A,B]}$ as illustrated at right in Figure \ref{fig:DilationIntersection}. The set $E_{C}=\{(a_{c},b_{c}):c \in C\}$ is a subset of $E$. The subsets $C$ of $(A)_{s}\cap (B)_{h(a,b)-s}$ that satisfy $ACB$ are those sets $C$ such that every $a \in A$ is a distance $s$ from some $c \in C$, and every $b \in B$ is a distance $h(a,b)-s$ from some $c' \in C$. In graph theory terms, $E_{C}$ will not isolate any vertices in $V$. Such a set is called an \emph{edge cover}.  

\begin{definition}
An \emph{edge cover} of a graph $G=(V,E)$ is a subset $E'$ of the set $E$ such that every vertex in $V$ is incident to at least one edge in $E'$.
\end{definition}

So $E_{C}$ is an edge cover of $G_{[A,B]}$. Thus, $\#([A,B])$ is equal to the number of edge covers of $G_{[A,B]}$. Similarly, every bipartite graph can be viewed as a finite configuration  \cite[Configuration Construction Theorem]{BLSSZ}. We also use the notation $\#(G)$ for the number of edge coverings of a graph $G$.

\section{Edge covers of complete bipartite graphs}

To understand which integers can appear as $\#([A,B])$ for a finite configuration $[A,B]$, we investigate edge covers of bipartite graphs. In an attempt to be systematic, we begin with the complete bipartite graphs, then study what happens when we begin to remove edges. We let $K_{m,n}$ denote the complete bipartite graph with parts $V_1$ and $V_2$, where $|V_1| = m$ and $|V_2| = n$. Throughout, we assume $m \leq n$. 

We can also calculate the number of edge covers of a bipartite graph using biadjacency matrices whose entries are all $0$ or $1$ (a $\{0,1\}$ matrix). The biadjacency matrix of a bipartite graph with parts $V_1$ and $V_2$ of size $m$ and $n$ is an $m \times n$ matrix whose $ij$th entry is $1$ if the $i$th vertex in $V_1$ is adjacent to the $j$th vertex in $V_2$ and is $0$ otherwise. Since an edge cover cannot isolate a vertex, the number of edge covers of such a bipartite graph is equal to the number of $\{0,1\}$ $m \times n$ matrices with no zero rows or columns. This number is well-known and can be calculated through a standard inclusion-exclusion principle argument. The next theorem provides the result. (Entry \seqnum{A048291} in the Online Encyclopedia of Integer Sequences (OEIS) gives this formula for $n \times n$ matrices.)

\begin{theorem}\label{thm:numsofcbg}
Let $E(m,n)$ be the number of edge covers of a $K_{m,n}$ complete bipartite graph. Then   
\begin{equation*}\label{eq:numsofcbg}
    E(m,n)=\sum_{j=0}^{m} {m \choose j} (-1)^j (2^{m-j}-1)^n.
\end{equation*}
\end{theorem}

With this result in hand, we proceed to determine the number of edge covers of the graphs that result from $K_{m,n}$ by removing one to three edges. 

\section{Edge covers of \texorpdfstring{$K_{m,n}$}{Km,n} minus one edge}

To calculate the number of edge covers of a complete bipartite graph that is missing edges, we use the following proposition from Honigs \cite{Honigs}. 

\begin{proposition} \label{prop:minus1edge}
Let $G$=$\{V,E\}$ be a graph. Let $v_{1}, v_{2} \in V$, and suppose $(v_{1}, v_{2}) \notin E$. Let $G'$ = $\{V,E'\}$ where $E'$=$E\cup\{(v_{1},v_{2})\}$. Then 
\begin{equation*}\label{eq:G'}
    \#(G') = 2\#(G)+\#(G-v_{1})+\#(G-v_{2})+\#(G-v_{1}-v_{2}).
\end{equation*}
\end{proposition}

We use Proposition \ref{prop:minus1edge} to determine the number of edge covers of graphs obtained from complete graphs by removing one, two, or three edges. We begin with removing one edge.  

\begin{theorem}\label{thm:removing1edge}
Let $G$ be a graph obtained from a complete bipartite graph $K_{m,n}$ after removing one edge. Then the number of edge covers of $G$ is $E_1(m,n)$ where
\begin{equation} \label{eq:one_edge}
    E_1(m,n) = \#(G)=\frac{1}{2}(E(m,n)-E(m-1,n)-E(m,n-1)-E(m-1,n-1)).
\end{equation}
\end{theorem}
(The function $E$ in Theorem \ref{thm:removing1edge} is defined in Theorem \ref{thm:numsofcbg}.) 

\begin{figure}[!ht]
\begin{center}
\begin{tabular}{cc}
\resizebox{!}{0.75in}{\includegraphics{Kmnmissing1.eps}} &amp;\resizebox{!}{0.75in}{\includegraphics{Kmnmissingv1.eps}} \\
$K_{m,n}$ minus the edge $(v_{1}, v_{2})$ &amp; $K_{m,n}$ minus the vertex $v_{1}$ \\
\resizebox{!}{0.75in}{\includegraphics{Kmnmissingv2.eps}} &amp; \resizebox{!}{0.75in}{\includegraphics{Kmnmissingv1v2.eps}} \\
$K_{m,n}$ minus vertex $v_{2}$ &amp; $K_{m,n}$ minus vertices missing vertices $v_{1}$ and $v_{2}$
\end{tabular}
\caption{Calculating $\#(K_{m,n} \text{ minus an edge})$.}  
\label{fig:Kmn-1edge}
\end{center}
\end{figure}

\begin{proof} Let the graph $G'$ be a complete bipartite graph and the graph $G$ be $G'$ missing one edge, $(v_1,w_1)$. Since we are only removing one edge, the completeness of $K_{m,n}$ implies that it does not matter which edge. Solving for $\#(G)$ in Proposition \ref{prop:minus1edge} gives \begin{equation*}\label{eq:proofeq2}
    \#(G) = \frac{1}{2}(\#(G')-\#(G-v_{1})-\#(G-w_{1})-\#(G-v_{1}-w_{1})).
\end{equation*}
As depicted in Figure \ref{fig:Kmn-1edge}, removing vertex $v_{1}$ from $G$ produces a $K_{m-1,n}$ graph. Removing vertex $w_{1}$ from $G$ produces a $K_{m, n-1}$ graph. Removing vertices $v_{1}$ and $w_{1}$ from $G$ produces a $K_{m-1, n-1}$ graph. Therefore
\begin{align*} 
    \#(G) &amp;= \frac{1}{2}(\#(K_{m,n})-\#(K_{m-1,n})-\#(K_{m,n-1})-\#(K_{m-1,n-1})) \\
    &amp;= \frac{1}{2}(E(m,n)-E(m-1,n)-E(m,n-1)-E(m-1,n-1)).
\end{align*}

\end{proof}


As a result of Theorem \ref{thm:removing1edge}, we obtain integer sequences by fixing the value of $m$ in calculations of $E_1(m,n)$ and letting $n$ change. As examples, we have the sequences given in Table \ref{T:K_mn_minus_edge} (sequences simplified with a computer algebra system). The first entry appears as sequences \seqnum{A024023} and \seqnum{A103453} in the OEIS. This graph theoretic approach to these sequences provides a new perspective from which to view these sequences

\begin{table}[ht]
\begin{center}
\renewcommand{\arraystretch}{1.3}
\begin{tabular}{c|c} 
$E_1(2,n)$ &amp; $3^{n-1}-1$ \\ \hline
$E_1(3,n)$ (\seqnum{A335608}) 	&amp; $3\cdot 7^{n-1}-5\cdot3^{n-1}+2$ \\ \hline
$E_1(4,n)$ (\seqnum{A335609})	&amp; $7\cdot 15^{n-1}-16 \cdot 7^{n-1}+4 \cdot 3^n -3$ \\ \hline
$E_1(5,n)$ (\seqnum{A335610})	&amp; $15 \cdot 31^{n-1} - 43 \cdot 15^{n-1}+46 \cdot 7^{n-1}-22 \cdot 3^{n-1}+4$ \\ \hline
$E_1(6,n)$ (\seqnum{A335611})	&amp; $ 31 \cdot 63^{n-1}-106 \cdot 31^{n-1}+145 \cdot 15^{n-1} - 100 \cdot 7^{n-1}+35 \cdot 3^{n-1}-5$
\end{tabular}
\caption{Sequences $(E_1(m,n))_{n \geq m}$.}
\label{T:K_mn_minus_edge}
\end{center}
\end{table}

It is not difficult to see from the sum (\ref{eq:one_edge}) and Theorem \ref{thm:numsofcbg} that the highest power exponential term in $E_1(m,n)$ comes from the summands $E(m,n)$ and $E(m,n-1)$. This term is 
\[\frac{1}{2}\bigl( (2^m-1)^n - (2^m-1)^{n-1}\bigr) = (2^{m-1}-1)(2^m-1)^{n-1}.\]
So the sequence $(E_1(m,n))_{n \geq m}$ behaves asymptotically as $(2^m-1)^{n-1}$ as $n$ increases. 

To conceptualize how edge covers of complete bipartite graphs missing one edge relate to the Hausdorff metric geometry, we consider the graph $G$ that is $K_{6,2}$ missing one edge. Since $E_1(6,2) = 242$ we know that $G$ has $242$ edge covers. The corresponding configuration $[A,B]$ with $A = \{a_1,a_2,a_3, a_4, a_5, a_6\}$ and $B = \{b_1,b_2\}$ is illustrated in Figure \ref{fig:conf_6_2_minus_edge}. Because $\#([A,B]) = \#(G)$, the number of distinct sets $C$ that lie on the segment $\overline{AB}$ in $\mathcal{H}(\mathbb{R}^N)$ at any fixed distance from $A$ is also $242$.


\begin{figure}[!ht]
\begin{center}
\resizebox{!}{1.75in}{\includegraphics{Conf_6_2_minus_edge.eps}} 
\caption{A configuration $[A,B]$.}  
\label{fig:conf_6_2_minus_edge}
\end{center}
\end{figure}

\section{Edge covers of \texorpdfstring{$K_{m,n}$}{Km,n} minus two edges}

The next step in our calculations of numbers of edge covers of subgraphs of complete bipartite graphs is to consider the case of removing two edges. When we remove two edges from a complete bipartite graph, there are three different cases for the number of edge covers of the graph that are based upon the vertices from which the two edges are removed. 

\begin{theorem}\label{thm:removing2edges}
Let $G$ be a $K_{m,n}$ complete bipartite graph missing two edges. Partition the vertex set $V$ of $G$ into two parts, $V_{1}$ and $V_{2}$, where $|V_{1}|=m$ and $|V_{2}|=n$. 
\begin{enumerate}
\item The number of edge covers of $G$ when the 2 removed edges are incident to the same vertex in $V_{1}$ and not incident to the same vertex in $V_2$ is $E_{2_1}(m,n)$ where
\begin{equation*}\label{eq:minus2case1}
   E_{2_1}(m,n) = \#(G)=\frac{1}{2}(E_{1}(m,n)-E(m-1,n)-E_{1}(m,n-1)-E(m-1,n-1)).
\end{equation*}
\item The number of edge covers of $G$ when the 2 removed edges are not incident to the same vertex in $V_{1}$ but are incident to the same vertex in $V_{2}$ is $E_{2_2}(m,n)$ where
\begin{equation*}\label{eq:minus2case2}
   E_{2_2}(m,n) = \#(G)=\frac{1}{2}(E_{1}(m,n)-E_{1}(m-1,n)-E(m,n-1)-E(m-1,n-1)).
\end{equation*}
\item The number of edge covers of $G$ when the 2 removed edges are not incident to the same vertex in $V_{1}$ and are not incident to the same vertex in $V_{2}$ is $E_{2_3}(m,n)$ where
\begin{equation*}\label{eq:minus2case3}
    E_{2_3}(m,n) = \#(G)=\frac{1}{2}(E_{1}(m,n)-E_{1}(m-1,n)-E_{1}(m,n-1)-E_{1}(m-1,n-1)).
\end{equation*}
\end{enumerate}
\end{theorem}

\begin{proof}
Assume the graph $G'$ is a $K_{m,n}$ complete bipartite graph missing one edge. Let $G$ be a graph obtained from $G'$ by removing an edge. Let the vertex set $V$ of $G$ be partitioned into two parts $V_{1} = \{v_1, v_2, \ldots, v_m\}$ and $V_{2} = \{w_1, w_2, \ldots, w_n\}$. We consider three different cases based on the incidence of the removed edges to certain vertices. The removed edges can be incident to the same vertex in $V_1$ but not in $V_2$, incident to the same vertex in $V_{2}$ but not in $V_{1}$, or not incident to the same vertex in $V_{1}$ or $V_{2}$, as illustrated from left to right, respectively, in Figure \ref{fig:Cases}.

\begin{figure}[!ht]
\begin{center}
\resizebox{!}{0.55in}{\includegraphics{Kmnmissing2_a.eps}}  \ \resizebox{!}{0.55in}{\includegraphics{Kmnmissing2_n.eps}}  \  \resizebox{!}{0.55in}{\includegraphics{Kmnmissing2_f.eps}}
\caption{Case 1, Case 2, and Case 3 for removing two edges.}
\label{fig:Cases}
\end{center}
\end{figure}



\begin{description}
\item[Case 1:]  Assume that the 2 removed edges in $G$ are incident to the same vertex in $V_{1}$ but are not incident to the same vertex in $V_{2}$. An illustration of such a graph $G$ can be seen at left in Figure \ref{fig:Case_1_2edges}. The edges $(v_{1},w_{1})$ and $(v_{1},w_{2})$ are missing, and both edges are incident to vertex $v_{1}$ in $V_{1}$. The graph of $G'$ can be seen at left in Figure \ref{fig:Case_1_2edges}. Notice that in the graph $G'$ only the edge $(v_{1},w_{1})$ is missing.
\begin{figure}[!ht]
\begin{center}
\begin{tabular}{cc}
\resizebox{!}{0.75in}{\includegraphics{Kmnmissing2_b.eps}} &amp; \resizebox{!}{0.75in}{\includegraphics{Kmnmissing2_a.eps}} \\
The graph $G'$	&amp; The graph $G$ 
\end{tabular}
\caption{Case 1: Removing two edges incident to the same vertex.}
\label{fig:Case_1_2edges}
\end{center}
\end{figure}

Since $G'$ is a $K_{m,n}$ complete bipartite graph missing one edge, $\#(G')=E_{1}(m,n)$.
\begin{figure}[!ht]
\begin{center}
\begin{tabular}{cc}
\resizebox{!}{0.75in}{\includegraphics{Kmnmissing2_c.eps}} &amp; \resizebox{!}{0.75in}{\includegraphics{Kmnmissing2_d.eps}} \\
The graph $G-v_{1}$		&amp; The graph $G-w_{2}$ 
\end{tabular}
\begin{tabular}{c}
\resizebox{!}{0.75in}{\includegraphics{Kmnmissing2_e.eps}}  \\
The graph $G-\{v_1,w_{2}\}$	
\end{tabular}
\caption{Case 1: Removing vertices from $G$.}
\label{fig:Case1_vertices}
\end{center}
\end{figure}

When we remove the vertex $v_{1}$ from $G$, the result is a $K_{m-1,n}$ complete bipartite graph, as seen at top left in Figure \ref{fig:Case1_vertices}. So $\#(G-v_{1})=E(m-1,n)$.

When we remove the vertex $w_{2}$ from $G$, the result is a $K_{m,n-1}$ complete bipartite graph missing one edge, as seen at top right in Figure \ref{fig:Case1_vertices}. So $\#(G-w_{2})=E_{1}(m,n-1)$.

When we remove vertices $v_{1}$ and $w_{2}$ from $G$, the result is a $K_{m-1,n-1}$ complete bipartite graph, as seen at bottom in Figure \ref{fig:Case1_vertices}. So $\#(G-v_{1}-w_{2})=E(m-1,n-1)$.

Proposition \ref{prop:minus1edge} then gives us 
\begin{equation*}
    \#(G)=\frac{1}{2}(E_{1}(m,n)-E(m-1,n)-E_{1}(m,n-1)-E(m-1,n-1)).
\end{equation*}

\item[Case 2:] In this case, the 2 removed edges in $G$ are not incident to the same vertex in $V_{1}$ but are incident to the same vertex in $V_{2}$. Note that this is the same case as case 1 with $m$ and $n$ interchanged. 

\item[Case 3:] In this case, the 2 removed edges in $G$ are not incident to the same vertex in $V_{1}$ and are not incident to the same vertex in $V_{2}$. An example of such a graph $G$ can be seen at right in Figure \ref{fig:Case_3_2edges}. The edges $(v_{1},w_{1})$ and $(v_{m},v_{n})$ are missing. Edge $(v_{1},w_{1})$ is incident to a different vertex in $V_{1}$ and a different vertex in $V_{2}$ than edge $(v_{m},w_{n})$. The graph of $G'$ can be seen at left in Figure \ref{fig:Case_3_2edges}. 
\begin{figure}[!ht]
\begin{center}
\begin{tabular}{cc}
\resizebox{!}{0.75in}{\includegraphics{Kmnmissing2_g.eps}}  &amp; \resizebox{!}{0.75in}{\includegraphics{Kmnmissing2_f.eps}}  \\
The graph $G'$	&amp; The graph $G$ 
\end{tabular}
\caption{Case 3: Removing two edges incident to the same vertex.}
\label{fig:Case_3_2edges}
\end{center}
\end{figure}

Since $G'$ is a $K_{m,n}$ complete bipartite graph missing one edge, $\#(G')=E_{1}(m,n)$.
\begin{figure}[!ht]
\begin{center}
\begin{tabular}{cc}
\resizebox{!}{0.75in}{\includegraphics{Kmnmissing2_h.eps}} &amp; \resizebox{!}{0.75in}{\includegraphics{Kmnmissing2_i.eps}} \\
The graph $G-v_{1}$		&amp; The graph $G-w_{1}$ 
\end{tabular}
\begin{tabular}{c}
\resizebox{!}{0.75in}{\includegraphics{Kmnmissing2_j.eps}}  \\
The graph $G-\{v_1,w_{1}\}$	
\end{tabular}
\caption{Case 3: Removing vertices from $G$.}
\label{fig:Case3_vertices}
\end{center}
\end{figure}

When we remove the vertex $v_{1}$ from $G$, the result is a $K_{m-1,n}$ complete bipartite graph missing one edge, as seen top left in Figure \ref{fig:Case3_vertices}, so $\#(G-v_{1})=E_{1}(m-1,n)$.

When we remove the vertex $w_{1}$ from $G$, the result is a $K_{m,n-1}$ complete bipartite graph missing one edge, as seen top right in Figure \ref{fig:Case3_vertices}, so $\#(G-w_{1})=E_{1}(m,n-1)$.

When we remove vertices $v_{1}$ and $w_{1}$ from $G$, the result is a $K_{m-1,n-1}$ complete bipartite graph missing one edge, as seen at bottom in Figure \ref{fig:Case3_vertices}, so $\#(G-v_{1}-w_{1})=E_{1}(m-1,n-1)$.

Proposition \ref{prop:minus1edge} then gives us 
\begin{equation*}
    \#(G)=\frac{1}{2}(E_{1}(m,n)-E_{1}(m-1,n)-E_{1}(m,n-1)-E_{1}(m-1,n-1)).
\end{equation*}
\end{description}
\end{proof}

As a result of Theorem \ref{thm:removing2edges}, there are three families of integer sequences given by $E_{2_i}(m,n)$ with $m$ fixed and $n$ varying. Some of these sequences are presented in Table \ref{T:K_mn_minus_two_edges}. The first entry is given in sequences \seqnum{A024023} and \seqnum{A103453} in the OEIS. Once again, this graph theoretic approach to these sequences provides a new perspective from which to view these sequences.

\begin{center}
\begin{longtable}[t]{c|c}
$E_{2_1}(2,n)$ &amp; $3^{n-2}-1$ \\ \hline
\dual{$E_{2_1}(3,n)$/(\seqnum{A335612})}&amp; $9\cdot 7^{n-2}-11\cdot3^{n-2}+2$ \\ \hline
\dual{$E_{2_1}(4,n)$/(\seqnum{A335613})}&amp; $49\cdot 15^{n-2}-76 \cdot 7^{n-2}+10 \cdot 3^{n-1} -3$ \\ \hline
\dual{$E_{2_1}(5,n)$/(\seqnum{A337416})}&amp; $225\cdot 31^{n-2} - 421 \cdot 15^{n-2}+250 \cdot 7^{n-2}-58 \cdot 3^{n-2}+4$ \\ \hline
\dual{$E_{2_1}(6,n)$/(\seqnum{A337417})}&amp; $961\cdot 63^{n-2}-2086 \cdot 31^{n-2}+1615 \cdot 15^{n-2} - 580 \cdot 7^{n-2}+95 \cdot 3^{n-2} -5$ \\ \hline
\dual{$E_{2_2}(3,n)$/(\seqnum{A337418})}&amp; $7^{n-1}-2\cdot3^{n-1}+1$ \\ \hline
\dual{$E_{2_2}(4,n)$/(\seqnum{A340173})}&amp;$3 \cdot 15^{n-1}-8 \cdot 7^{n-1}+7 \cdot 3^{n-1} -2$ \\ \hline
\dual{$E_{2_2}(5,n)$/(\seqnum{A340174})}&amp; $7 \cdot 31^{n-1} - 23 \cdot 15^{n-1}+4 \cdot 7^{n}-5 \cdot 3^{n}+3$ \\ \hline
\dual{$E_{2_2}(6,n)$/(\seqnum{A340175})}&amp; $15 \cdot 63^{n-1}-58 \cdot 31^{n-1}+89 \cdot 15^{n-1} - 68 \cdot 7^{n-1}+26 \cdot 3^{n-1}-4$ \\ \hline
$E_{2_3}(2,n)$ &amp; $3^{n-2}$ \\ \hline
\dual{$E_{2_3}(3,n)$/(\seqnum{A340199})}&amp; $9\cdot 7^{n-2}-7\cdot3^{n-2}+1$ \\ \hline
\dual{$E_{2_3}(4,n)$/(\seqnum{A340200})}&amp; $49\cdot 15^{n-2}-60 \cdot 7^{n-2}+22 \cdot 3^{n-2} -2$ \\ \hline
\dual{$E_{2_3}(5,n)$/(\seqnum{A340201})}&amp; $225 \cdot 31^{n-2} - 357 \cdot 15^{n-2}+202 \cdot 7^{n-2}-46 \cdot 3^{n-2}+3$ \\ \hline
\dual{$E_{2_3}(6,n)$/(\seqnum{A340897})}&amp; $ 961 \cdot 63^{n-2}-1830 \cdot 31^{n-2}+1359 \cdot 15^{n-2} - 484 \cdot 7^{n-2}+79 \cdot 3^{n-2}-4$\\
\caption{Sequences $(E_{2_k}(m,n))_{n \geq m}$.}
\label{T:K_mn_minus_two_edges}
\end{longtable}
\end{center}
			
As an example of interpreting edge covers of complete bipartite graphs from a geometric perspective, consider the configurations $[A, B]$ (left) and $[A', B']$ (right) as shown in Figure \ref{fig:conf_6_2_minus_2_edges}, where $A = A' = \{a_1,a_2,a_3, a_4, a_5, a_6\}$ and $B = B' = \{b_1,b_2\}$. Both configurations have corresponding $K_{2,6}$ graphs missing two edges. We have $\#([A, B]) = E_{2_3}(2, 6) = 81$ and $\#([A', B']) = E_{2_1} (2, 6) = 80$, so there are $81$ distinct sets that lie on the line segment $\overline{AB}$ at each fixed distance from $A$, and $80$ distinct sets that lie on the line segment $\overline{A'B'}$ at each distance from $A'$. These findings correspond to the sequence $3^{n-2}$ and the fifth term of \seqnum{A024023} in the OEIS, respectively.

\begin{figure}[!ht]
\begin{center}
\resizebox{!}{1.75in}{\includegraphics{Conf_6_2_minus_2_edges_a.eps}} \hspace{0.5in} \resizebox{!}{1.75in}{\includegraphics{Conf_6_2_minus_2_edges_b.eps}} 
\caption{Two complete configurations missing two edges.}  
\label{fig:conf_6_2_minus_2_edges}
\end{center}
\end{figure}

\section{Edge covers of \texorpdfstring{$K_{m,n}$}{Km,n} minus three edges}

We will take one more step in our calculations of number of edge covers and determine the number of edge covers of a $K_{m,n}$ complete bipartite graph missing 3 edges. In this case, there are 6 different possibilities for the removal of edges as indicated in Theorem \ref{thm:removing3edges}. The functions $E_{2_1}$, $E_{2_2}$, and $E_{2_3}$ are defined in Theorem \ref{thm:removing2edges}. 

\begin{theorem}\label{thm:removing3edges}
Let $G$ be a $K_{m,n}$ complete bipartite graph missing three edges. Let the vertex set $V$
 of $G$ be partitioned into two parts $V_{1}$ and $V_{2}$ where $|V_{1}|=m$ and $|V_{2}|=n$. 
 \begin{enumerate}
\item The number of edge covers of $G$ when all 3 removed edges are incident to the same vertex in $V_{1}$ but are incident to different vertices in $V_{2}$ is $E_{3_1}(m,n)$ where
\begin{equation}\label{eq:minus3case1}
   E_{3_1}(m,n) = \#(G)=\frac{1}{2}(E_{2_{1}}(m,n)-E(m-1,n)-E_{2_{1}}(m,n-1)-E(m-1,n-1)).
\end{equation}
\item The number of edge covers of $G$ when all 3 removed edges are incident to different vertices in $V_{1}$ and none of the removed edges are incident to the same vertex in $V_{2}$ is $ E_{3_2}(m,n)$ where
\begin{equation}\label{eq:minus3case2}
    E_{3_2}(m,n) = \#(G)=\frac{1}{2}(E_{2_{3}}(m,n)-E_{2_{3}}(m-1,n)-E_{2_{3}}(m,n-1)-E_{2_{3}}(m-1,n-1)).
\end{equation}
 \item The number of edge covers of $G$ when all 3 removed edges are incident to different vertices in $V_{1}$ but all 3 removed edges are incident to the same vertex in $V_{2}$ (note that this equation returns a value of 0 in the $K_{3,n}$ case) is $E_{3_3}(m,n)$ where
\begin{equation}\label{eq:minus3case3}
    E_{3_3}(m,n) = \#(G)=\frac{1}{2}(E_{2_{2}}(m,n)-E_{2_{2}}(m-1,n)-E(m,n-1)-E(m-1,n-1)).
\end{equation}
\item The number of edge covers of $G$ when exactly 2 of the removed edges are incident to the same vertex in $V_{1}$ but none of the removed edges are incident to the same vertex in $V_{2}$ is $E_{3_4}(m,n)$ where
\begin{equation}\label{eq:minus3case4}
    E_{3_4}(m,n) = \#(G)=\frac{1}{2}(E_{2_{3}}(m,n)-E_{1}(m-1,n)-E_{2_{3}}(m,n-1)-E_{1}(m-1,n-1)).
\end{equation}
 \item The number of edge covers of $G$ when all 3 removed edges are incident to different vertices in $V_{1}$ but exactly 2 removed edges are incident to the same vertex in $V_{2}$ is $E_{3_5}(m,n)$ where
\begin{equation}\label{eq:minus3case5}
    E_{3_5}(m,n) = \#(G)=\frac{1}{2}(E_{2_{3}}(m,n)-E_{2_{3}}(m-1,n)-E_{1}(m,n-1)-E_{1}(m-1,n-1)).
\end{equation}
\item The number of edge covers of $G$ when exactly 2 removed edges are incident to the same vertex in $V_{1}$ and exactly 2 removed edges are incident to the same vertex in $V_{2}$ is $E_{3_6}(m,n)$ where
\begin{equation}\label{eq:minus3case6}
    E_{3_6}(m,n) = \#(G)=\frac{1}{2}(E_{2_{3}}(m,n)-E_{1}(m-1,n)-E_{1}(m,n-1)-E(m-1,n-1)).
\end{equation}
\end{enumerate}
\end{theorem}

\begin{proof}
Assume the graph $G'$ is a $K_{m,n}$ complete bipartite graph missing two edges. Let the graph $G$ be a graph obtained from $G'$ by removing an edge. Let the vertex set $V$ of $G$ be partitioned into two parts $V_{1}$ and $V_{2}$ where $|V_{1}|=m$ and $|V_{2}|=n$. We consider six different cases based on the incidence of the removed edges to certain vertices. The possible cases are those listed in Theorem \ref{thm:removing3edges}.

\begin{description}
\item[Case 1:] In this case, all 3 removed edges are incident to the same vertex in $V_{1}$. An example of a graph of $G'$, with edges $(v_{1},w_{2})$ and $(v_{1},w_{3})$ missing, and a corresponding graph $G$ missing the additional edge $(v_1,w_1)$ can be seen in Figure \ref{fig:M3_1}. All 3 edges are incident to $v_{1}$ in $V_{1}$ but are incident to different vertices in $V_{2}$. 
\begin{figure}[!ht]
\begin{center}
 \resizebox{!}{2.5in}{\includegraphics{Missing3Case1.eps}} 
  \caption{The graphs for case 1.}
  \label{fig:M3_1}
\end{center}
\end{figure}

Since $G'$ is a $K_{m,n}$ complete bipartite graph missing two edges that are incident to the same vertex in $V_{1}$ but different vertices in $V_{2}$, we have that $\#(G')=E_{2_{1}}(m,n)$.

When we remove the vertex $v_{1}$ from $G$, the result is a $K_{m-1,n}$ complete bipartite graph, as seen in Figure \ref{fig:M3_1}. So $\#(G-v_{1})=E(m-1,n)$.

When we remove the vertex $w_{1}$ from $G$, the result is a $K_{m,n-1}$ complete bipartite graph missing two edges that are incident to the same vertex in $V_{1}$ but incident to different vertices in $V_{2}$, as seen in Figure \ref{fig:M3_1}. So $\#(G-w_{1})=E_{2_{1}}(m,n-1)$.

When we remove vertices $v_{1}$ and $w_{1}$ from $G$, the result is a $K_{m-1,n-1}$ complete bipartite graph, as seen in Figure \ref{fig:M3_1}. This means we can use $E$ to calculate $\#(G-v_{1}-w_{1})$, so $\#(G-v_{1}-w_{1})=E(m-1,n-1)$. 

Proposition \ref{prop:minus1edge} then gives us
\begin{equation*}
    \#(G)=\frac{1}{2}(E_{2_{1}}(m,n)-E(m-1,n)-E_{2_{1}}(m,n-1)-E(m-1,n-1)).
\end{equation*}

\item[Case 2:] In this case, all 3 edges are incident to different vertices in $V_{1}$ and none of the vertices are incident to the same vertex in $V_{2}$. An example of a graph $G'$ missing vertices $(v_2, w_2)$ and $(v_{m}, w_{n})$ and a corresponding $G$ missing the additional edge $(v_1,w_1)$ can be seen in Figure \ref{fig:M3_2}. None of the edges are incident to the same vertices in $V_{1}$ or in $V_{2}$.

\begin{figure}[!ht]
\begin{center}
  \includegraphics[width=15cm, origin=c]{Missing3Case2.eps}
  \caption{The graphs for case 2.}
  \label{fig:M3_2}
\end{center}
\end{figure}

Since $G'$ is a $K_{m,n}$ complete bipartite graph missing two edges that are incident to different vertices in $V_{1}$ and $V_{2}$, as seen in Figure \ref{fig:M3_2}, we can use $E_{2_{3}}$ to calculate $\#(G')$, so $\#(G')=E_{2_{3}}(m,n)$.

When we remove the vertex $v_{1}$ from $G$, the result is a $K_{m-1,n}$ complete bipartite graph missing two edges that are incident to different vertices in $V_{1}$ and $V_{2}$, as seen in Figure \ref{fig:M3_2}. This means we can use $E_{2_{3}}$ to calculate $\#(G-v_{1})$, so $\#(G-v_{1})=E_{2_{3}}(m-1,n)$.

When we remove the vertex $w_{1}$ from $G$, the result is a $K_{m,n-1}$ complete bipartite graph missing two edges that are incident to different vertices in $V_{1}$ and $V_{2}$, as seen in Figure \ref{fig:M3_2}. This means we can use $E_{2_{3}}$ to calculate $\#(G-w_1)$, so $\#(G-w_1)=E_{2_{3}}(m,n-1)$.

When we remove vertices $v_{1}$ and $w_1$ from $G$, the result is a $K_{m-1,n-1}$ complete bipartite graph missing two edges that are incident to different vertices in $V_{1}$ and $V_{2}$, as seen in Figure \ref{fig:M3_2}. This means we can use $E_{2_{3}}$ to calculate $\#(G-v_{1}-w_1)$, so $\#(G-v_{1}-w_1)=E_{2_{3}}(m-1,n-1)$.

Proposition \ref{prop:minus1edge} then gives us
\begin{equation*}
    \#(G)=\frac{1}{2}(E_{2_{3}}(m,n)-E_{2_{3}}(m-1,n)-E_{2_{3}}(m,n-1)-E_{2_{3}}(m-1,n-1)).
\end{equation*}

\item[Case 3:] In this case, all 3 edges removed are incident to different vertices in $V_{1}$ but all 3 removed edges are incident to the same vertex in $V_{2}$. An example of a $G'$ missing edges $(v_2,w_1)$ and $(v_3,w_1)$ along with a corresponding $G$ missing the additional edge $(v_1,w_1)$ can be seen in Figure \ref{fig:M3_3}. All 3 edges are incident to different vertices in $V_{1}$ but are incident to vertex $w_1$ in $V_{2}$.
\begin{figure}[!ht]
\begin{center}
  \includegraphics[width=16cm, origin=c]{Missing3Case3.eps}
  \caption{The graphs for case 3.}
  \label{fig:M3_3}
\end{center}
\end{figure}

Since $G'$ is a $K_{m,n}$ complete bipartite graph missing two edges that are incident to different vertices in $V_{1}$ but the same vertex in $V_{2}$, as seen in Figure \ref{fig:M3_3}, we can use $E_{2_{2}}$ to calculate $\#(G')$, so $\#(G')=E_{2_{2}}(m,n)$.

When we remove the vertex $v_{1}$ from $G$, the result is a $K_{m-1,n}$ complete bipartite graph missing two edges that are incident to different vertices in $V_{1}$ but the same vertex in $V_{2}$, as seen in Figure \ref{fig:M3_3}. This means we can use $E_{2_{2}}$ to calculate $\#(G-v_{1})$, so $\#(G-v_{1})=E_{2_{2}}(m-1,n)$.

When we remove the vertex $w_1$ from $G$, the result is a $K_{m,n-1}$ complete bipartite graph, as seen in Figure \ref{fig:M3_3}. This means we can use $E$ to calculate $\#(G-w_1)$, so $\#(G-w_1)=E(m,n-1)$.

When we remove vertices $v_{1}$ and $w_1$ from $G$, the result is a $K_{m-1,n-1}$ complete bipartite graph, as seen in Figure \ref{fig:M3_3}. This means we can use $E$ to calculate $\#(G-v_{1}-w_1)$, so $\#(G-v_{1}-w_1)=E(m-1,n-1)$.

Proposition \ref{prop:minus1edge} then gives us
\begin{equation*}
    \#(G)=\frac{1}{2}(E_{2_{2}}(m,n)-E_{2_{2}}(m-1,n)-E(m,n-1)-E(m-1,n-1)).
\end{equation*}

\item[Case 4:] In this case, exactly 2 of the removed edges are incident to the same vertex in $V_{1}$, but none of the removed edges are incident to the same vertex in $V_{2}$. An example of a graph $G'$ missing edges $(v_1,w_2)$ and $(v_2,w_3)$ along with a corresponding graph $G$ missing the additional edge $(v_1,w_1)$ can be seen in Figure \ref{fig:M3_4}. There are 2 edges incident to $v_{1}$ in $V_{1}$ while one edge is not. All of the edges are incident to different vertices in $V_{2}$.
\begin{figure}[!ht]
\begin{center}
  \includegraphics[width=15cm, origin=c]{Missing3Case4.eps}
  \caption{The graphs for case 4.}
  \label{fig:M3_4}
\end{center}
\end{figure}

Since $G'$ is a $K_{m,n}$ complete bipartite graph missing two edges that are incident to different vertices in $V_{1}$ and $V_{2}$, as seen in Figure \ref{fig:M3_4}, we can use $E_{2_{3}}$ to calculate $\#(G')$, so $\#(G')=E_{2_{3}}(m,n)$.

When we remove the vertex $v_{1}$ from $G$, the result is a $K_{m-1,n}$ complete bipartite graph missing one edge, as seen in Figure \ref{fig:M3_4}. This means we can use $E_{1}$ to calculate $\#(G-v_{1})$, so $\#(G-v_{1})=E_{1}(m-1,n)$.

When we remove the vertex $w_1$ from $G$, the result is a $K_{m,n-1}$ complete bipartite graph missing two edges that are incident to different vertices in $V_{1}$ and different vertices in $V_{2}$, as seen in Figure \ref{fig:M3_4}. This means we can use $E_{2_{3}}$ to calculate $\#(G-w_1)$, so $\#(G-w_1)=E_{2_{3}}(m,n-1)$.

When we remove vertices $v_{1}$ and $w_1$ from $G$, the result is a $K_{m-1,n-1}$ complete bipartite graph missing one edge, as seen in Figure \ref{fig:M3_4}. This means we can use $E_{1}$ to calculate $\#(G-v_{1}-w_1)$, so $\#(G-v_{1}-v_{2})=E_{1}(m-1,n-1)$.

Proposition \ref{prop:minus1edge} then gives us
\begin{equation*}
    \#(G)=\frac{1}{2}(E_{2_{3}}(m,n)-E_{1}(m-1,n)-E_{2_{3}}(m,n-1)-E_{1}(m-1,n-1)).
\end{equation*}

\item[Case 5:] In this case, all 3 removed edges are incident to different vertices in $V_{1}$, but exactly 2 removed edges are incident to the same vertex in $V_{2}$. An example of a graph $G'$ missing edges $(v_2,w_1)$ and $(v_3,w_3)$ along with a corresponding graph $G$ missing the additional edge $(v_1,w_1)$ can be seen in Figure \ref{fig:M3_5}. All 3 edges are incident to different vertices in $V_{1}$, but 2 of the edges are incident to $w_1$ in $V_{2}$.

\begin{figure}[!ht]
\begin{center}
  \includegraphics[width=16cm, origin=c]{Missing3Case5.eps}
  \caption{The graphs for case 5.}
  \label{fig:M3_5}
\end{center}
\end{figure}

Since $G'$ is a $K_{m,n}$ complete bipartite graph missing two edges that are incident to different vertices in $V_{1}$ and $V_{2}$, as seen in Figure \ref{fig:M3_5}, we can use $E_{2_{3}}$ to calculate $\#(G')$, so $\#(G')=E_{2_{3}}(m,n)$.

When we remove the vertex $v_{1}$ from $G$, the result is a $K_{m-1,n}$ complete bipartite graph missing two edges that are incident to different vertices in $V_{1}$ and $V_{2}$, as seen in Figure \ref{fig:M3_5}. This means we can use $E_{2_{3}}$ to calculate $\#(G-v_{1})$, so $\#(G-v_{1})=E_{2_{3}}(m-1,n)$.

When we remove the vertex $w_1$ from $G$, the result is a $K_{m,n-1}$ complete bipartite graph missing one edge, as seen in Figure \ref{fig:M3_5}. This means we can use $E_{1}$ to calculate $\#(G-w_1)$, so $\#(G-w_1)=E_{1}(m,n-1)$.

When we remove vertices $v_{1}$ and $w_1$ from $G$, the result is a $K_{m-1,n-1}$ complete bipartite graph missing one edge, as seen in Figure \ref{fig:M3_5}. This means we can use $E_{1}$ to calculate $\#(G-v_{1}-w_1)$, so $\#(G-v_{1}-w_1)=E_{1}(m-1,n-1)$.

Proposition \ref{prop:minus1edge} then gives us
\begin{equation*}
    \#(G)=\frac{1}{2}(E_{2_{3}}(m,n)-E_{2_{3}}(m-1,n)-E_{1}(m,n-1)-E_{1}(m-1,n-1)).
\end{equation*}

\item[Case 6:] In this case, exactly 2 removed edges are incident to the same vertex in $V_{1}$ and exactly 2 removed edges are incident to the same vertex in $V_{2}$. An example of a graph $G'$ missing edges $(v_2,w_1)$ and $(v_1,w_2)$ along with a corresponding graph $G$ missing the additional edge $(v_1,w_1)$ can be seen in Figure \ref{fig:M3_6}. Exactly two edges are incident to $v_{1}$ in $V_{1}$, and exactly two edges are incident to $w_1$ in $V_{2}$.
\begin{figure}[!ht]
\begin{center}
  \includegraphics[width=15cm, origin=c]{Missing3Case6.eps}
  \caption{The graphs for case 6.}
  \label{fig:M3_6}
\end{center}
\end{figure}

Since $G'$ is a $K_{m,n}$ complete bipartite graph missing two edges that are incident to different vertices in $V_{1}$ and $V_{2}$, as seen in Figure \ref{fig:M3_6}, we can use $E_{2_{3}}$ to calculate $\#(G')$, so $\#(G')=E_{2_{3}}(m,n)$.

When we remove the vertex $v_{1}$ from $G$, the result is a $K_{m-1,n}$ complete bipartite graph missing one edge, as seen in Figure \ref{fig:M3_6}. This means we can use $E_{1}$ to calculate $\#(G-v_{1})$, so $\#(G-v_{1})=E_{1}(m-1,n)$.

When we remove the vertex $w_1$ from $G$, the result is a $K_{m,n-1}$ complete bipartite graph missing one edge, as seen in Figure \ref{fig:M3_6}. This means we can use $E_{1}$ to calculate $\#(G-w_1)$, so $\#(G-w_1)=E_{1}(m,n-1)$.

When we remove vertices $v_{1}$ and $w_1$ from $G$, the result is a $K_{m-1,n-1}$ complete bipartite graph, as seen in Figure \ref{fig:M3_6}. This means we can use $E$ to calculate $\#(G-v_{1}-w_1)$, so $\#(G-v_{1}-w_1)=E(m-1,n-1)$.

Proposition \ref{prop:minus1edge} then gives us
\begin{equation*}
    \#(G)=\frac{1}{2}(E_{2_{3}}(m,n)-E_{1}(m-1,n)-E_{1}(m,n-1)-E(m-1,n-1)).
\end{equation*}
\end{description}
\end{proof}

A few of the sequences given by Theorem \ref{thm:removing3edges} are shown in Table \ref{T:K_mn_minus_three_edges}. The first entry is given in sequences \seqnum{A024023} and \seqnum{A103453}---the remainder had not been previously recorded in the OEIS. 

Theorem \ref{thm:removing3edges} once again informs us about the number of sets that lie on certain line segments in $\mathcal{H}(\mathbb{R}^N)$ at a fixed distance from one of the endpoints. For example, if $A = \{a_1,a_2,a_3, a_4, a_5, a_6\}$ and $B = \{b_1,b_2\}$, then $\#([A,B]) = E_{3_1}(2,6) = 26$ when $[A,B]$ is the configuration shown at left in Figure \ref{fig:conf_6_2_minus_3_edges}, and $\#([A,B]) = E_{3_4}(2,6) = 27$ when $[A,B]$ is the configuration shown at right in Figure \ref{fig:conf_6_2_minus_3_edges}.  
\begin{figure}[!ht]
\begin{center}
\resizebox{!}{1.75in}{\includegraphics{Conf_6_2_minus_3_edges_a.eps}} \hspace{0.5in} \resizebox{!}{1.75in}{\includegraphics{Conf_6_2_minus_3_edges_b.eps}} 
\caption{Two complete configurations missing three edges.}  
\label{fig:conf_6_2_minus_3_edges}
\end{center}
\end{figure}


\section{Conclusion}

All of the sequences $(E_1(k,n))$ for $k$ from $3$ to $6$, $(E_{2_i}(k,n))$ for $i$ from $1$ to $3$ and $k$ from $3$ to $6$, and $(E_{3_i}(k,n))$ for $i$ from $1$ to $6$ and $k$ from $4$ to $6$ in this investigation were previously uncatalogued integer sequences in the OEIS. It is likely that line segments in $\mathcal{H}(\mathbb{R}^N)$ (and edge covers of graphs) can provide many more examples of new integer sequences. 

\begin{table}[H]
\centering
\resizebox{.8\textwidth}{!}{%
\begin{tabular}{c|c}
$E_{3_1}(2,n)$ 	&amp;$3^{n-3} - 1$ \\ \hline
\dual{$E_{3_1}(3,n)$/(\seqnum{A340898})}    &amp; $27 \cdot 7^{n-3}-29 \cdot 3^{n-3} + 2$ \\ \hline
\dual{$E_{3_1}(4,n)$/(\seqnum{A340899})}	 &amp; $343 \cdot 15^{n-3}-424 \cdot 7^{n-3}+28 \cdot 3^{n-2} - 3$ \\ \hline
\dual{$E_{3_1}(5,n)$/(\seqnum{A342580})}		&amp; $3375 \cdot 31^{n-3}-4747 \cdot 15^{n-3}-166 \cdot 3^{n-3} +1534 \cdot 7^{n-3}+4$ \\ \hline
\dual{$E_{3_1}(6,n)$/(\seqnum{A342796})}		&amp; $29791 \cdot 63^{n-3}-46666 \cdot 31^{n-3}+20305 \cdot 15^{n-3} -3700 \cdot 7^{n-3} + 275 \cdot 3^{n-3}- 5$ \\ \hline
\dual{$E_{3_2}(3,n)$/(\seqnum{A342850})}		&amp; $27 \cdot 7^{n-3}-3^{n-1}$ \\ \hline
\dual{$E_{3_2}(4,n)$/(\seqnum{A340403})}		&amp; $343 \cdot 15^{n-3}-216 \cdot 7^{n-3} +4 \cdot 3^{n-1}-1$ \\ \hline
\dual{$E_{3_2}(5,n)$/(\seqnum{A340404})}		&amp; $3375 \cdot 31^{n-3}-2891 \cdot 15^{n-3}+846 \cdot 7^{n-3}-10 \cdot 3^{n-1}+2$ \\ \hline
\dual{$E_{3_2}(6,n)$/(\seqnum{A340405})}		&amp; $29791 \cdot 63^{n-3}-31050 \cdot 31^{n-3}+12369 \cdot 15^{n-3} -2260 \cdot 7^{n-3} + 19\cdot 3^{n-1}- 3$ \\ \hline
\dual{$E_{3_3}(4,n)$/(\seqnum{A340433})}		&amp; $15^{n-1}-3 \cdot 7^{n-1} +3^{n}-1$ \\ \hline
\dual{$E_{3_3}(5,n)$/(\seqnum{A340434})}		&amp; $3\cdot 31^{n-1}-11 \cdot 15^{n-1}+15 \cdot 7^{n-1}- 3^{n-1}+2$ \\ \hline
\dual{$E_{3_3}(6,n)$/(\seqnum{A340435})}	&amp; $7 \cdot 63^{n-1}-30\cdot 31^{n-1}+51 \cdot 15^{n-1} -43 \cdot 7^{n-1} + 6\cdot 3^{n}- 3$ \\ \hline
\dual{$E_{3_4}(3,n)$/(\seqnum{A340436})} 		&amp; $27 \cdot 7^{n-3}-13 \cdot 3^{n-3}+1$ \\ \hline
\dual{$E_{3_4}(4,n)$/(\seqnum{A340437})}		&amp; $343 \cdot 15^{n-3}-264 \cdot 7^{n-3} +52 \cdot 3^{n-3}-2$ \\ \hline
\dual{$E_{3_4}(5,n)$/(\seqnum{A340438})}		&amp; $3375 \cdot 31^{n-3}-3339 \cdot 15^{n-3}+1054 \cdot 7^{n-3}-118 \cdot 3^{n-3}+3$ \\ \hline
\dual{$E_{3_4}(6,n)$/(\seqnum{A341551})}		&amp; $29791 \cdot 63^{n-3}-34890 \cdot 31^{n-3}+14673 \cdot 15^{n-3} -2740 \cdot 7^{n-3} + 211\cdot 3^{n-3}- 4$ \\ \hline
\dual{$E_{3_5}(3,n)$/(\seqnum{A341552})}		&amp; $3 \cdot 7^{n-2}-2 \cdot 3^{n-2}$ \\ \hline
\dual{$E_{3_5}(4,n)$/(\seqnum{A341553})}		&amp; $21 \cdot 15^{n-2}-4 \cdot 7^{n-1} +11 \cdot 3^{n-2}-1$ \\ \hline
\dual{$E_{3_5}(5,n)$/(\seqnum{A342327})}		&amp; $105 \cdot 31^{n-2}-185 \cdot 15^{n-2}+116 \cdot 7^{n-2}-29 \cdot 3^{n-2}+2$ \\ \hline
\dual{$E_{3_5}(6,n)$/(\seqnum{A342328})}		&amp; $465 \cdot 63^{n-2}-982 \cdot 31^{n-2}+807 \cdot 15^{n-2} -316 \cdot 7^{n-2} + 56\cdot 3^{n-2}- 3$ \\ \hline
\dual{$E_{3_6}(3,n)$/(\seqnum{A343372})}		&amp; $3 \cdot 7^{n-2}-4 \cdot 3^{n-2}+1$ \\ \hline
\dual{$E_{3_6}(4,n)$/(\seqnum{A343373})}		&amp; $21 \cdot 15^{n-2}-36 \cdot 7^{n-2} +17 \cdot 3^{n-2}-2$ \\ \hline
\dual{$E_{3_6}(5,n)$/(\seqnum{A343374})}		&amp; $105 \cdot 31^{n-2}-217 \cdot 15^{n-2}+148 \cdot 7^{n-2}-13 \cdot 3^{n-1}+3$ \\ \hline
\dual{$E_{3_6}(6,n)$/(\seqnum{A343800})}		&amp; $465 \cdot 63^{n-2}-1110 \cdot 31^{n-2}+967 \cdot 15^{n-2} -388 \cdot 7^{n-2} + 70\cdot 3^{n-2}- 4$ \\
\end{tabular}%
}
\caption{Sequences $(E_{3_k}(m,n))_{n \geq n}$.}
\label{T:K_mn_minus_three_edges}
\end{table}

\section{Acknowledgments}

This work was supported by National Science Foundation grant DMS-1659113. The authors also thank Grand Valley State University for hosting and supporting a Research Experiences for Undergraduates program.


\begin{thebibliography}{9}

\bibitem{Barnsley} M. F. Barnsley, \emph{Fractals Everywhere}, Second Edition, Academic Press Professional, 1998.

\bibitem{BLSSZ} C. Blackburn, K. Lund, S. Schlicker, P. Sigmon, and A. Zupan, A missing prime configuration in the Hausdorff metric geometry, \textit{J. Geom.} \textbf{92} (2009), 28--59. 

\bibitem{Blumenthal}
L. M. Blumenthal, \emph{Theory and Applications of Distance Geometry}, Oxford University Press, 1953.

\bibitem{Bog}
A. Bogdewicz, Some properties of hyperspaces, \textit{Demonstr. Math.} \textbf{33} (2000), 135--149.

\bibitem{BMMS} D. Braun, J. Mayberry, A. Malagon, and S. Schlicker, A singular introduction to the Hausdorff metric geometry,  \textit{Pi Mu Epsilon J.} (2005), 129--138.

\bibitem{Edgar} G. A. Edgar, \emph{Measure, Topology, and Fractal Geometry}, Springer-Verlag, 1990.

\bibitem{Honigs} K. Honigs, Missing edge coverings of bipartite graphs and the geometry of the Hausdorff metric, \textit{J. Geom.} \textbf{104} (2013), 107--125. 

\bibitem{LSS} K. Lund, P. Sigmon, and S. Schlicker, Fibonacci sequences in the space of compact sets, \emph{Involve} \textbf{1} (2008), 197--215.

\bibitem{Ovsyannikov} Z. N. Ovsyannikov, The number of edge covers of bipartite graphs or of shortest paths with fixed endpoints in the space of compact sets in $\mathbf{R}^n$ (English Translation), \textit{Dokl. Math.} \textbf{93}  (2016), 65--68.

\bibitem{polygonalchains} S. Schlicker, L. Morales, and D. Schultheis,  Polygonal chain sequences in the space of compact sets, \emph{J. Integer Seq.} \textbf{12}  (2009). 

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2020 {\it Mathematics Subject Classification}:
Primary 51F99; Secondary 05C99, 11B83.

\noindent \emph{Keywords: } 
Hausdorff metric, configurations, bipartite graphs, edge covers, integer sequences.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A024023},
\seqnum{A048291},
\seqnum{A103453},
\seqnum{A335608},
\seqnum{A335609},
\seqnum{A335610},
\seqnum{A335611},
\seqnum{A335612},
\seqnum{A335613},
\seqnum{A337416},
\seqnum{A337417},
\seqnum{A337418},
\seqnum{A340173},
\seqnum{A340174},
\seqnum{A340175},
\seqnum{A340199},
\seqnum{A340200},
\seqnum{A340201},
\seqnum{A340403},
\seqnum{A340404},
\seqnum{A340405},
\seqnum{A340433},
\seqnum{A340434},
\seqnum{A340435},
\seqnum{A340436},
\seqnum{A340437},
\seqnum{A340438},
\seqnum{A340897},
\seqnum{A340898},
\seqnum{A340899},
\seqnum{A341551},
\seqnum{A341552},
\seqnum{A341553},
\seqnum{A342327},
\seqnum{A342328},
\seqnum{A342580},
\seqnum{A342796},
\seqnum{A342850},
\seqnum{A343372},
\seqnum{A343373},
\seqnum{A343374},
\seqnum{A343800}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received September 13 2021;
revised versions received  March 2 2023; June 18 2023.
Published in {\it Journal of Integer Sequences}, June 19 2023.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                
</pre></body></html>