定义：
对于二部图上的一个匹配，构造一个长度为的布尔串，第位记为，其满足：当且仅当在中被匹配。我们称是的匹配串。
Notation abusingly，我们让同时成为一个函数，，其中。，其中。对于这两个函数，如果找不到对应的函数值，那就返回报错字符。比方说，如果在中是unmatched的，那。
我们还用字典序的概念比较的大小，举例而言，本文中的字典序大于，因为。
定理一：
对于任意二部图，存在一个它的最大匹配及其匹配串，使得对于任意匹配及其匹配串，都有。
这个定理表明了最大匹配的一种“贪心”性质，形象地说就是，总存在一个最大匹配，它可以由某种贪心的匹配方式导出。
证明：
假设定理一不成立，即存在，其中是所有最大匹配的匹配串中字典序最大的那个（如果有多个符合条件的就任取一个）。
设。显然。便代表此处被匹配给的左部点编号。
我们构造这样两个链条（数列）：
初始化，
让这两个链条一直持续到的第一个时刻。
这两个链条的形象解释是：我们假设了和一开始每个时刻的已匹配数都一样，但是在时刻，匹配了，而却没有匹配。的匹配数暂时比多一个。在此刻将匹配给了。
也就是说，我们访问的第个左点，其被匹配时刻为（或者说它被匹配给了第个右点），其编号为。（初始化）
接下来，我们访问中同一编号的左点，因此，其被匹配时刻为。（第一行递推式）
接下来，我们访问中同一时刻被匹配的左点，因此，其编号为。（第二行递推式）
注意到，该匹配轮流访问和中的左点（为奇数时是，偶数时是）。
理解了这两个链条，我们给出如下断言：
设。构造一个新匹配，其匹配过程和一致，但是将替换为。则。
由于也是最大匹配，这和“是所有最大匹配的匹配串中字典序最大的那个”的条件不符。
矛盾。
因此定理一是正确的。
读者可以自行验证以下问题：
为什么一定会有的时刻？
为什么替换后就有？
好的，现在我们可以谈一谈标题说的东西。
考虑周期固定为，周期数为的可复用资源二部图匹配问题。（相关设定参见“Online Bipartite Matching with Reusable Resources”）
我们现在考虑这样一类特殊情形：
也就是所谓的图的结构周期性地重复。我们把符合这类条件的图的集合记为。
我们将在第个周期的结构记为。
注意到，如果，则将的最大匹配重复次就是在该问题下的最大匹配。
那么，我们可以对每一周期的在线匹配竞争系数分别度量，不妨将第个周期的竞争系数记为。
猜想1：
对于算法，若，则。
更进一步的，设的字典序最大的匹配串为。
猜想2：
对于算法，若，则。
（根据定理1，可注意到猜想2蕴含猜想1）
更新：
猜想2是错的，“1302”有可能永远也变不成“1230”。
但是下面的修改版尚未找到反例：
猜想3：
对于算法，若且不存在这样的最大匹配，其结束时间超过，则。