Online Algorithm for Fractional Matchings with Edge Arrivals in Graphs of Maximum Degree Three Kanstantsin Pashkovich, Thomas Snow Abstract We study online algorithms for maximum cardinality matchings with edge arrivals in graphs of low degree. Buchbinder, Segev, and Tkach showed that no online algorithm for maximum cardinality fractional matchings can achieve a competitive ratio larger than 4 / ( 9 − 5 ) ≈ 0.5914 4/(9-\sqrt{5})\approx 0.5914 even for graphs of maximum degree three. The negative result of Buchbinder et al. holds even when the graph is bipartite and edges are revealed according to vertex arrivals, i.e. once a vertex arrives, all edges are revealed that include the newly arrived vertex and one of the previously arrived vertices. In this work, we complement the negative result of Buchbinder et al. by providing an online algorithm for maximum cardinality fractional matchings with a competitive ratio at least 4 / ( 9 − 5 ) ≈ 0.5914 4/(9-\sqrt{5})\approx 0.5914 for graphs of maximum degree three. We also demonstrate that no online algorithm for maximum cardinality integral matchings can have the competitive guarantee 0.5807 0.5807 , establishing a gap between integral and fractional matchings for graphs of maximum degree three. Note that the work of Buchbinder et al. shows that for graphs of maximum degree two, there is no such gap between fractional and integral matchings, because for both of them the best achievable competitive ratio is 2 / 3 2/3 . Also, our results demonstrate that for graphs of maximum degree three best possible competitive ratios for fractional matchings are the same in the vertex arrival and in the edge arrival models. 1 Introduction Matchings constitute an extensively studied area of mathematics and theoretical computer science with various practical applications. Indeed, matchings arise in different areas of our everyday lives: job placements for students, assigning riders to drivers on a ride-sharing platform, providing advertisement spots, etc. Some of these matchings have an online nature since the edges or vertices in the underlying graph appear at certain timepoints and are available only in a specific time frame. In this work, we study maximum cardinality matchings in an adversarial edge arrival model. In this model, at every timepoint a new edge arrives. In the integral matching case, upon the arrival of a new edge, we need to immediately and irrevocably decide whether to include this new edge in our current matching. In the fractional matching case, we need to irrevocably select a value for each new edge such that for every vertex, the sum of values on incident edges is always at most one. To make these decisions, we rely on online algorithms. To estimate the performance of an online algorithm, we select as a benchmark the cardinality of a maximum matching in the already "arrived" graph. In this paper, we focus mainly on the adversarial edge arrival model in graphs of maximum degree three. We determine the best competitive ratio of online algorithms for fractional matchings in these graphs. To do this, we provide an online algorithm that achieves the guarantee 4/(9-\sqrt{5})\approx 0.5914 on these graphs, where 4/(9-\sqrt{5})\approx 0.5914 equals the corresponding upper bound obtained in [ 3 ] . Due to the construction in [ 3 ] , for graphs of maximum degree three, the best possible competitive ratio remains the same regardless of whether one considers general or bipartite graphs, and whether one considers the vertex arrival or edge arrival models. Additionally, we show that the guarantee 4/(9-\sqrt{5})\approx 0.5914 cannot be achieved on graphs of maximum degree four; we also show that the above guarantee cannot be achieved for integral matchings in general graphs of maximum degree three. In general, we know that the vertex arrival and edge arrival models lead to different competitive ratios for fractional matchings. Indeed, the results of [ 17 ] show that for general graphs, online algorithms can achieve a competitive ratio 0.526 in the vertex arrival model. The results of [ 7 ] show that no online algorithm can achieve a guarantee larger than 0.5 in the edge arrival model, even for bipartite graphs. Thus, at a certain value of the maximum degree, the best competitive ratio for the vertex arrival order is strictly larger than the competitive ratio for the edge arrival order; our work shows that this degree should be at least four. 1.1 Our Results In our work, we focus on online algorithms for fractional matchings in the adversarial edge arrival model. [ 3 ] established a series of results for online matchings in the edge arrival model when the underlying graph has a bounded maximum degree. In particular, Buchbinder, Segev, and Tkach showed that no online algorithm for maximum cardinality fractional matchings can achieve a competitive ratio larger than 4/(9-\sqrt{5})\approx 0.5914 even for graphs of maximum degree three. The negative result in [ 3 ] holds even when the graph is a forest and edges are revealed according to vertex arrivals. In this work, we provide an online algorithm for maximum cardinality fractional matchings with a competitive ratio at least 4/(9-\sqrt{5})\approx 0.5914 for graphs of maximum degree three, thus showing that 4/(9-\sqrt{5})\approx 0.5914 is the best competitive ratio for graphs of degree three. So, for maximum cardinality fractional matchings, our result demonstrates that for graphs of maximum degree three, the competitive ratios are the same for the edge arrival and vertex arrival models. We also show that no online algorithm can achieve a guarantee larger than 0.5807 for integral matchings in graphs of maximum degree three. Thus, unlike for graphs of maximum degree two [ 3 ] , our results establish a gap between the best achievable competitive ratios for fractional and integral matchings in graphs of maximum degree three. Next, we show that the guarantee of 4/(9-\sqrt{5})\approx 0.5914 is not achievable in the graphs of maximum degree four. To show this, we provide an instance such that no online algorithm for maximum cardinality fractional matching can achieve a guarantee larger than \approx 0.58884 on it in the edge arrival model. Another important contribution in [ 3 ] is an elegant algorithm, so called MinIndex Algorithm. Buchbinder et al. show that MinIndex achieves the best possible guarantees both in the case of fractional and integral matchings when the maximum degree is at most two. We show that the guarantee achieved by the MinIndex algorithm is at most 5/9\approx 0.555 in forests with maximum degree three. Our result improves on the upper bound 4/7\approx 0.571 shown by Buchbinder et al. Note that Buchbinder et al. showed that the competitive ratio of the MinIndex algorithm equals 5/9 for both integral and fractional matchings on forests, but their upper bound construction involves graphs with maximum degree four. 1.2 Related Work The seminal paper [ 12 ] studied online matchings in the setting where the graph is bipartite and the vertices in one part appear over time. Each time a vertex appears, all of its incident edges are revealed, and one needs to make an irrevocable decision on which one of these edges to include in the matching, if any. [ 12 ] provided a ranking algorithm that achieves the best possible competitive ratio of (1-1/e) . In the general adversarial edge arrival model, Gamlath et al. [ 7 ] showed that no online algorithm has a competitive ratio larger than 1/2+1/(2d+2) when the maximum degree is d , even on bipartite graphs. Thus, [ 7 ] showed that no online algorithm can beat the greedy algorithm’s competitive ratio 1/2 , even in bipartite graphs. These results hold for both fractional and integral matchings. In [ 3 ] , an algorithm with the competitive guarantee 2/3 was provided for graphs with maximum degree two, which was shown to be optimal. [ 3 ] showed that no online algorithm can achieve a competitive ratio larger than 4/(9-\sqrt{5})\approx 0.5914 even on forests with maximum degree three in the vertex arrival model. Further upper bounds were obtained in [ 6 ] , [ 10 ] . In the edge arrival model for bipartite graphs, where all edges appear in s batches [ 13 ] developed an algorithm with a guarantee 1/2+1/(2^{s+2}-2) for both integral and fractional matchings, where s is the number of batches. For s=2 , the competitive ratio becomes 2/3 , and it is also optimal. [ 9 ] developed an online algorithm with a competitive ratio larger than the competitive ratio of the greedy algorithm for bipartite graphs and random uniform edge arrival orders. Online stochastic matchings with oblivious adversarial edge arrival order in bipartite graphs were studied in [ 8 ] . In [ 8 ] , an algorithm was developed that achieves a guarantee of 0.503 in the above stochastic model, and they complement this result with an upper bound of 2/3 on any achievable guarantee. There was an extensive study of the edge arrival models under the assumption of free edge disposal, i.e. an already selected edge can be disposed of at later timepoints. For the weighted version of the problem, a deterministic algorithm with guarantee 1/(3+2\sqrt{2}) was provided in [ 14 ] ; moreover, this guarantee was shown to be optimal among deterministic algorithms [ 1 ] . Later, [ 6 ] provided a randomized algorithm with a guarantee of 0.1867 for this model. There was further progress on upper bounds for possible guarantees of randomized algorithms in this model, see [ 6 ] , [ 11 ] . The degree of the underlying graph was also studied in the context of online matching algorithms for rounding fractional matchings [ 4 ] , [ 16 ] , [ 2 ] . For a comprehensive overview of results on online matchings, we refer the readers to the surveys [ 15 ] , [ 5 ] , and to a recent survey [ 11 ] . 1.3 Our Techniques Our online algorithm and its analysis demonstrate that the upper bound 4/(9-\sqrt{5})\approx 0.5914 from [ 3 ] is the best possible for graphs with maximum degree three. Our online algorithm is inspired by the construction from [ 3 ] . Indeed, to obtain their upper bound, [ 3 ] construct instances such that every online algorithm with the guarantee 4/(9-\sqrt{5})\approx 0.5914 on them should maintain a certain fractional matching. We refer to these instances as "consistent instances". We use the structure of the fractional matchings from [ 3 ] on consistent instances as "building blocks" in our algorithm. We partition the edges from the consistent instances into two types of edges "path edges" and "spokes". Our algorithm attempts to greedily construct consistent instances from arriving edges, identifying some of the arrived edges as path edges and some as spokes. Naturally, the algorithm is not able to group all edges into consistent instances, and thus, we identify the remaining edges as "bridges". For the path edges and spokes, our algorithm attempts to keep their values close to the values as in fractional matchings from [ 3 ] . For the bridges, we need to consider several cases to carefully assign the value of the resulting fractional matching. Our algorithm keeps both a primal solution and a dual solution, i.e. it keeps both the values of a fractional matching and the values of a fractional vertex cover. The values of the fractional cover are used mainly for the analysis, and with the exception of spokes, the assignment of values for the fractional matching does not rely on them. 2 Our Algorithm In this section, we first provide the intuition behind our algorithm that comes from the upper bound construction in [ 3 ] . Afterwards, we state our algorithm in full detail and provide all necessary notions. 2.1 Consistent Instances First, let us introduce a particular hard instance for graphs of maximum degree three which was constructed in [ 3 ] . A consistent instance with n rounds contains the following edges 1. e_{1}=v^{l}_{1}v^{r}_{1} . 2. e^{l}_{i}=v^{l}_{i-1}v^{l}_{i} and e^{r}_{i}=v^{r}_{i-1}v^{r}_{i} for i=2,\dots,n . 3. \hat{e}^{l}_{i}=v^{l}_{i}\hat{v}^{l}_{i} and \hat{e}^{r}_{i}=v^{r}_{i}\hat{v}^{r}_{i} for i=1,\dots,n-2 . Here, first the edge e_{1} arrives, then with each further i=2,\dots,n the edges e^{l}_{i} and e^{r}_{i} arrive. After that, the edges \hat{e}^{l}_{i} and \hat{e}^{r}_{i} arrive for i=1,\dots,n-2 . See Figure 1 for an example of a consistent instance with n=4 . Buchbinder et al. show that any online algorithm for the fractional matching problem achieves the guarantee at most c:=4/(9-\sqrt{5})\approx 0.5914 on the consistent instances defined above. Since the consistent instances correspond to bipartite graphs, the same upper bound c=4/(9-\sqrt{5})\approx 0.5914 holds for the guarantee of online algorithms for integral matchings. v^{l}_{1} v^{r}_{1} v^{r}_{2} v^{r}_{3} v^{r}_{4} v^{l}_{2} v^{l}_{3} v^{l}_{4} \hat{v}^{l}_{1} \hat{v}^{r}_{1} \hat{v}^{l}_{2} \hat{v}^{r}_{2} e_{1} e^{l}_{2} e^{r}_{2} e^{l}_{3} e^{r}_{3} e^{l}_{4} e^{r}_{4} \hat{e}^{l}_{1} \hat{e}^{r}_{1} \hat{e}^{l}_{2} \hat{e}^{r}_{2} Figure 1: Example of a consistent instance with n=4 rounds. 2.2 Edge Types Our algorithm tries to greedily construct consistent instances from the arriving edges. To do that systematically, we define three types of edges, so each edge is assigned one of these types upon its arrival: • type 1, path edges . • type 2, spokes . • type 3, bridges . Intuitively, the path edges are the edges associated with 1 and 2 in the definition of consistent instances, while spokes are the edges associated with 3 in the definition of consistent instances; see Figure 1 . Roughly speaking, bridges are the edges that run between two different consistent instances that our algorithm constructed so far. We would like to note that bridges and spokes are more tricky objects for our algorithm than the above intuition may suggest. To keep the exposition concise, we define the function \text{type}(\cdot) . For each subset of edges A\subseteq E , the value \text{type}(A) equals (t_{1},t_{2},t_{3}) , where t_{1} , t_{2}, and t_{3} equal the number of edges in A of type 1, type 2, and type 3, respectively. The most challenging case for us is to identify bridges and to assign them appropriate values. For these purposes, our algorithm is looking for special combinations of types when an edge e=uv arrives. In particular our algorithms relies on the following set \left\{\text{type}\left(\delta(u)\setminus\{e\}\right),\,\text{type}\left(\delta(v)\setminus\{e\}\right)\right\} in the current graph G after the edge e arrived. If the above set lies in \mathcal{B}:=\{\{(1,0,0)\},\{(1,0,0),(0,1,0)\},\{(1,1,0),(1,0,0)\},\{(0,2,0),(1,0,0)\}\} then an arrived edge e is considered to be a bridge by our algorithm. For the sake of exposition, we also define the function \text{ends}(\cdot) . For each edge e=uv\in E , we have \text{ends}(uv):=\{u,v\} . 2.3 Determining Types for the Arriving Edge Note that our algorithm assumes that the graph has maximum degree at most three at every timepoint. Let us describe how we assign the type to a newly arrived edge e=uv . Here, we work with the graph G that refers to the graph after the arrival of the edge e . So, \delta(u) stands for the edges incident to the vertex u in G , and \deg(u) stands for the degree of u in G , etc. For each f in E\setminus\{e\} , the value y_{f} represents the value assigned to the edge f in the fractional matching constructed before the arrival of e . Table 1 illustrates \text{type}(e) for the arriving edge e=uv assigned by our algorithm. As follows from the table, the type of e=uv depends on \text{type}\left(\delta(u)\setminus\{e\}\right) and \text{type}(\delta(v)\setminus\{e\}) . There are several special cases. In Table 1 these cases are represented by enclosing the type of e=uv in a box. In these special cases, both u and v have degree 3 in the graph G , so without loss of generality, in these cases, we assume 1-\sum_{f\in\delta(u)\setminus\{e\}}y_{f}\leq 1-\sum_{f\in\delta(v)\setminus\{e\}}y_{f}\,. The empty cells in Table 1 correspond to impossible combinations of \text{type}\left(\delta(u)\setminus\{e\}\right) and \text{type}(\delta(v)\setminus\{e\}) . Table 1: Type assignment for the newly arrived edge e=uv . (0,0,0) (1,0,0) (0,1,0) (0,0,1) (1,1,0) (1,0,1) (0,1,1) (2,0,0) (0,2,0) (0,0,2) (0,0,0) 1 1 1 1 2 2 2 1 (1,0,0) 1 3 3 3 2 2 2 3 (0,1,0) 1 3 1 1 2 2 2 1 (0,0,1) (1,1,0) 1 3 1 1 1 1 1 1 (1,0,1) 2 2 2 2 2 2 2 2 (0,1,1) 2 2 2 2 2 2 2 2 (2,0,0) 2 2 2 2 2 2 2 2 (0,2,0) 1 3 1 1 1 1 1 1 (0,0,2) 2.4 Fractional Matching in Consistent Instances Now that we have provided an idea of how our algorithm assigns a type to the arriving edge, let us provide a general idea of how we intend to construct a fractional matching. The upper bound proof by Buchbinder et al. showed that for an online algorithm to achieve a competitive ratio on consistent instances defined in Section 2.1 , the algorithm has to output a very specific fractional matching on these instances. Let us define the values that should appear in the resulting fractional matching as per [ 3 ] . For this, let us define the following values \widetilde{y}_{1}:=c,\,\widetilde{y}_{2}:=\frac{c}{2}\quad\text{and}\quad\widetilde{y}_{3}:=\frac{5c-2}{2} and for natural n , n\geq 4 let us define \widetilde{y}_{n}:=\frac{(3F_{n}+F_{n-2}-2)c-2F_{n}+2}{2}\,, where \phi:=\frac{1+\sqrt{5}}{2} , \psi:=1-\phi and F_{n}:=\frac{\phi^{n}-\psi^{n}}{\sqrt{5}} . So \phi is the golden ratio, and F_{n} is the n -th Fibonacci number. We note the following useful property, the proof of which can be found in Appendix A , property ( 7 ) of Lemma A.1 , for all natural n we have 1-\widetilde{y}_{n}-\widetilde{y}_{n+1}=c-\widetilde{y}_{n+2} . In particular, we use 1-\widetilde{y}_{n}-\widetilde{y}_{n+1} and c-\widetilde{y}_{n+2} interchangeably. The proof for the upper bound in [ 3 ] showed that for the algorithm to achieve a competitive ratio c on consistent instances, the algorithm needs to assign the following edge values (subject to symmetry breaking), see Section 2.1 : 1. e_{1}=v^{l}_{1}v^{r}_{1} has to be assigned \widetilde{y}_{1} . 2. e^{l}_{i}=v^{l}_{i-1}v^{l}_{i} and e^{r}_{i}=v^{r}_{i-1}v^{r}_{i} for i=2,\dots,n have to be assigned \widetilde{y}_{n} . 3. \hat{e}^{l}_{i}=v^{l}_{i}\hat{v}^{l}_{i} and \hat{e}^{r}_{i}=v^{r}_{i}\hat{v}^{r}_{i} for i=1,\dots,n-2 have to be assigned 1-\widetilde{y}_{n}-\widetilde{y}_{n+1} . Our algorithm tries to follow these value assignments on path edges and spokes, but the presence of bridges requires us to select more nuanced assignments even on path edges and spokes. In particular, we make more careful value assignments for edges that are bridges or are incident to a bridge upon their arrival. 2.5 Algorithm We defer the formal definition of Algorithm 1 to Appendix 3 , which relies heavily on the primal-dual methodology. Without loss of generality, we assume that for the arriving edge e=uv that \deg(u)\geq\deg(v) . Algorithm 1 is a primal-dual algorithm. The algorithm produces a fractional matching by assigning each arrived edge e\in E a nonnegative value y_{e} such that at every timepoint and for every vertex w we have \sum_{f\in\delta(w)}y_{f} is at most 1 . Moreover, the algorithm produces a fractional vertex cover by keeping and updating nonnegative values x_{w} for each vertex w\in V . At every timepoint and for every arrived edge e=uv , we have that x_{u}+x_{v} is at least c . Thus, at every timepoint, the values x_{w} , w\in V scaled by 1/c produce a fractional vertex cover for the graph G . 2.5.1 Value Assignments in Consistent Instances Thus, to prove that c is indeed the guarantee of our online algorithm, it suffices to prove that at every timepoint the sum of all y_{e} , e\in E equals the sum of all x_{w} , w\in V . Let us provide an intuition about how the algorithm preserves this equality by updating x_{w} , w\in V . Figure 2 demonstrates the increases in the values x_{w} , w\in\left\{v^{l}_{i},v^{l}_{i-1},v^{l}_{i+1},\hat{v}^{l}_{i}\right\} after the arrivals of their incident edges in the consistent instances from Section 2.1 . For example, after the edge v^{l}_{i}v^{l}_{i+1} arrives, the edge v^{l}_{i}v^{l}_{i+1} gets value \widetilde{y}_{i} and the values x_{w} , w\in\left\{v^{l}_{i},v^{l}_{i+1}\right\} are increased by \widetilde{y}_{i}-(c-\widetilde{y}_{i+1}) and c-\widetilde{y}_{i+1} , respectively. We would like to emphasize that Figure 2 depicts an ideal situation for constructing the fractional matchings and updating the fractional vertex cover. Our algorithm attempts to mimic this ideal behavior upon the arrival of path edges and spokes. v^{l}_{i} v^{l}_{i-1} v^{l}_{i+1} v^{l}_{i+2} \hat{v}^{l}_{i} \dots \dots \widetilde{y}_{i-1} \widetilde{y}_{i} \widetilde{y}_{i+1} c-\widetilde{y}_{i+1} \widetilde{y}_{i-1}-(c-\widetilde{y}_{i}) c-\widetilde{y}_{i} \widetilde{y}_{i}-(c-\widetilde{y}_{i+1}) c-\widetilde{y}_{i+1} \widetilde{y}_{i+1}-(c-\widetilde{y}_{i+2}) c-\widetilde{y}_{i+2} \widetilde{y}_{i+2}-(c-\widetilde{y}_{i+3}) c-\widetilde{y}_{i-1} c-\widetilde{y}_{i+1} Figure 2: The construction of the fractional matching and increases in the fractional vertex cover, when Algorithm 1 has a consistent instance as an input. 2.5.2 Position Indicators and Endpoints’ distinction in Consistent Instances Even in the ideal situation depicted in Figure 2 , to assign values to path edges, Algorithm 1 relies on determining the exact position of such edges in the consistent instance. To make sure that Algorithm 1 has access to these positions, we keep a position indicator n_{f} for each path edge f in the graph. For example, in a consistent instance when f=v^{l}_{i}v^{l}_{i+1} we have n_{f}=i+1 ; and when f=v^{l}_{1}v^{r}_{i} we have n_{f}=1 . Already in the consistent instances, the endpoints of the arriving edges could have different properties. For example, if an arriving edge is identified as a path edge in a consistent instance, then one of its endpoints has degree one and the other endpoint has degree two (immediately after this arrival). To keep track of these different properties, for some edges e , the algorithm identifies one of the endpoints as z(e) and another endpoint as w(e) . In particular, this is crucial for the analysis of path edges and spokes. For example, in Figure 2 for the path edge f=v^{l}_{i}v^{l}_{i+1} we have z(f)=v^{l}_{i} and w(f)=v^{l}_{i+1} , similarly for the path edge f=v^{l}_{i+1}v^{l}_{i+2} we have z(f)=v^{l}_{i+1} and w(f)=v^{l}_{i+2} . For the spoke f=v^{l}_{i}\hat{v}^{l}_{i} in Figure 2 , we have z(f)=v^{l}_{i} and w(f)=\hat{v}^{l}_{i} . 2.5.3 Partition into Consistent Instances and Bridges With the cover construction depicted in Figure 2 in mind, Algorithm 1 utilizes this construction by loosely partitioning the arriving edges into subgraphs of the consistent instance, with some exceptions; namely, bridges. The purpose of bridges is to connect, not necessarily distinct, partitions. To see how the fractional cover changes, consider, for example, the updates in the fractional cover upon the arrival of a path edge in lines 35 and 36 of Algorithm 1 . These updates are identical to the ones depicted in 2 except that in certain cases we cannot use the value \widetilde{y}_{n_{e}} from the ideal case depicted in Figure 2 but we have to use the actually assigned value y_{e} . In a similar way, we can see the updates in the fractional cover upon the arrival of a spoke, see line 30 of Algorithm 1 . Recall from Section 2.2 that an edge e=uv is assigned to be a bridge if and only if \{\delta(u)\setminus\{e\},\,\delta(v)\setminus\{e\}\} is in the set \mathcal{B} . Consider Figure 3 , where we assume that all edges but b_{1} , b_{2} , b_{3} , b_{4} , b_{5} , s_{1} , s_{2} arrive first in some specific order, and then the edges b_{1} , b_{2} , b_{3} , b_{4} , b_{5} arrive, and then s_{1} , s_{2} arrive. Now, before the arrival of b_{5} , both of the endpoints of b_{5} are incident only to one path edge each. Thus since \{(1,0,0)\} is in \mathcal{B} , the edge b_{5} is assigned to be a bridge. Even though it is helpful to think about Algorithm 1 as an algorithm partitioning the arrived path edges and spokes into consistent instances, this intuition does not always extend to spokes. In particular, some of the edges are assigned to be a spoke even though they do not "naturally fit" in any consistent instance. For example, before s_{1} arrives, one of its endpoints is incident to a bridge b_{1} and a path edge, while the other endpoint is incident to no edges. Due to the presence of the bridge b_{1} , the edge s_{1} is not assigned to be a path edge but to be a spoke by Algorithm 1 . Generally, an edge becomes such a spoke when, after its arrival, precisely one of its endpoints has degree 3 and is incident to a bridge. \hobbyinit \hobby@initial@pt \hobbysetparams \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbysetparams \hobbygenusepath \hobbyinit \hobbysetparams \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbyaddpoint \hobbysetparams \hobbygenusepath b_{1} b_{2} b_{3} b_{4} b_{5} s_{1} s_{2} Figure 3: An example of a potential partition indirectly maintained by Algorithm 1 (subject to arrival order) into subgraphs of the consistent instances. Here, the straight green edges represent path edges, the wavy red edges represent spokes, and the dashed blue edges represent bridges. 2.5.4 The Difficulty of Bridges Bridges are divided into four classes determined by the incident edges to their endpointscmcm see the definition based on \mathcal{B} . Intuitivelycmcm an edge e is assigned a bridge when both endpoints are already in consistent instances in the current partitioncmcm and it is not clear to which consistent instance the edge e should be added. In this casecmcm the edge e is assigned a bridge and e attempts to fulfill the role it would be givencmcm as if it were assigned to each partition individually. For instancecmcm in Figure 3 as the bridge b_{1} arrives it is not immediately clear which consistent instance b_{1} should join. In this casecmcm b_{1} prevents the paths’ “growth" in these two consistent instances beyond the endpoints of b_{1} . After the arrival of b_{1} cmcm the algorithm needs to account for the possibility of future edges incident to b_{1} cmcm and to do that the algorithm needs to update x and y appropriately. The main obstacle for finding an appropriate x and y update is the possibility of future spokes incident to b_{1} . Sincecmcm as explained above, b_{1} prevented the paths’ “growth" in two consistent instances, we might want the x update to happen as in the case where b_{1} is just a new path edge in both consistent instances. However, this is not always possible. For instance, consider the case where the two path edges adjacent to b_{1} are assigned \widetilde{y}_{1}=c and \widetilde{y}_{2}=c/2 , that is, the first and second edges in their respective paths. So if we were to adhere to the structure in Figure 2 , we would require the dual solution x to increase by \widetilde{y}_{2}-(c-\widetilde{y}_{3}) for one of the endpoints and \widetilde{y}_{3}-(c-\widetilde{y}_{4}) for the other. However, to do so the assignment to b_{1} would have to be at least \widetilde{y}_{2}-(c-\widetilde{y}_{3})+\widetilde{y}_{3}-(c-\widetilde{y}_{4})=\frac{c}{2}-(c-\frac{5c-2}{2})+\frac{5c-2}{2}-\left(c-(4c-2)\right)=\frac{15c}{2}-4\,. However, as c+\frac{15c}{2}-4>1 , this assignment to b_{1} is not feasible. To circumvent this, the algorithm capitalizes on the structure of the future edges incident to b_{1} , and this structure allows the algorithm to assign b_{1} a substantially smaller value than c+\frac{15c}{2}-4 . Similarly, one can handle the case when one of the endpoints of an arriving bridge is incident to a previously arrived spoke. This case can be seen in bridges b_{2} , b_{3} , and b_{4} in Figure 3 . Let u be the common endpoint of the arriving bridge and existing spoke. In this situation, our algorithm guarantees that the value of x_{u} after the arrival of b_{1} is at least the value of x_{u} at the moment when the spoke arrived. This ensures that x remains a feasible dual solution; in particular, that the corresponding constraint for the spoke is satisfied by x even after the arrival of b_{1} . 3 Algorithm Definition and Main Properties Algorithm 1 Online Algorithm for Maximum Cardinality Fractional Matchings in Graphs of Maximum Degree Three 1: While e=uv arrives (Assume \text{deg}(v)\leq\text{deg}(u) ) 2: if \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}\in\mathcal{B} then 3: \text{type}(e)\leftarrow 3 4: if \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,1,0),(1,0,0)\} then 5: Let f_{1},f_{2}\in\delta(u) , \text{type}(f_{1})=1,\text{type}(f_{2})=2 , and f_{3}\in\delta(v) , \text{type}(f_{3})=1 6: y_{e}\leftarrow\max\{\widetilde{y}_{n_{f_{3}}+1}-y_{f_{2}}-\min\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\},0\} 7: x_{u}\leftarrow x_{u}+y_{e}-\max\{\widetilde{y}_{n_{f_{3}}+1}-y_{f_{2}},0\} 8: x_{v}\leftarrow x_{v}+\max\{\widetilde{y}_{n_{f_{3}}+1}-y_{f_{2}},0\} 9: else if \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(0,2,0),(1,0,0)\} then 10: Let f_{v}\in\delta(v)\setminus\{e\} 11: y_{e}\leftarrow\max\{\widetilde{y}_{n_{f_{v}}+1}-\max\{y_{f}\mid f\in\delta(u)\setminus\{e\}\},0\} 12: x_{v}\leftarrow x_{v}+y_{e} 13: else if \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,0,0)\} then 14: Let f_{u}\in\delta(u)\setminus\{e\} , f_{v}\in\delta(v)\setminus\{e\} 15: Let z(e)\in\text{ends}(e) s.t \widetilde{y}_{n_{f_{z(e)}}+1}=\min\{\widetilde{y}_{n_{f}+1},\mid f\in\{f_{u},f_{v}\}\} , and w(e)\in\text{ends}(e)\setminus\{z(e)\} 16: y_{e}\leftarrow\widetilde{y}_{n_{f_{z(e)}}+1}-(c-\widetilde{y}_{n_{f_{w(e)}}+1}) 17: x_{z(e)}\leftarrow x_{z(e)}+\widetilde{y}_{n_{f_{z(e)}}+1}-\min\{\frac{c}{2},1-y_{f_{z(e)}}-y_{e}\} 18: x_{w(e)}\leftarrow x_{w(e)}+\widetilde{y}_{n_{f_{w(e)}}+1}-\max\{\frac{c}{2},c-(1-y_{f_{z(e)}}-y_{e})\} 19: else if \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,0,0),(0,1,0)\} then 20: f_{1},f_{2}\in\delta(\text{ends}(e)),\text{type}(f_{i})=i,z(e)\in\text{ends}(e)\cap\text{ends}(f_{1}),w(e)\in\text{ends}(e)\cap\text{ends}(f_{2}) 21: y_{e}\leftarrow\max\{\widetilde{y}_{n_{f_{1}}+1}-y_{f_{2}},0\} 22: x_{z(e)}\leftarrow x_{z(e)}+y_{e}-\max\{(2c-1)-y_{f_{2}},0\} 23: x_{w(e)}\leftarrow x_{w(e)}+\max\{(2c-1)-y_{f_{2}},0\} 24: end if 25: else 26: (z(e),w(e))\leftarrow\begin{cases}(v,u)&\mbox{if $\text{deg}(v)==3$ and $1-\sum_{f\in\delta(v)\setminus\{e\}}y_{f}<1-\sum_{f\in\delta(u)\setminus\{e\}}y_{f}$}\\ (u,v)&\mbox{\text{otherwise }}\end{cases} 27: if \text{deg}(z(e))==3 and \text{type}(\delta(z(e))\setminus\{e\})\notin\{(0,2,0),(1,1,0)\} then 28: y_{e}\leftarrow c-x_{z(e)} 29: \text{type}(e)\leftarrow 2 30: x_{w(e)}\leftarrow x_{w(e)}+y_{e} 31: else 32: n_{e}\leftarrow\max\left\{\{n_{f}+1\mid f\in\delta(z(e)\setminus\{e\}),\text{type}(f)=1\}\cup\{1\}\right\} 33: y_{e}\leftarrow\min\{\widetilde{y}_{n_{e}},1-\sum_{f\in\delta(z(e))\setminus\{e\}}y_{f}\} 34: \text{type}(e)\leftarrow 1 35: x_{z(e)}\leftarrow x_{z(e)}+y_{e}-(c-\widetilde{y}_{n_{e}+1}) 36: x_{w(e)}\leftarrow x_{w(e)}+(c-\widetilde{y}_{n_{e}+1}) 37: end if 38: end if Having stated Algorithm 1 , we need to demonstrate two things: that the algorithm outputs a feasible fractional matching and that the algorithm achieves the desired guarantee c . To accomplish this, we prove that at every timepoint the results of computations satisfy all of the properties stated in the next lemma. The crucial properties for the correctness and guarantee are the properties P1 , P2 , and P3 from the below lemma, while other key properties for technical arguments are stated in Appendix B . We defer the proof of Lemma 3.1 to Appendix B . Lemma 3.1 (Main Properties) . Let the underlying graph have maximum degree three. At every timepoint the values y and x computed by Algorithm 1 satisfy the following properties: P1 \sum_{u\in V}x_{u}=\sum_{e\in E}y_{e} . P2 for all e=uv\in E we have x_{u}+x_{v}\geq c . P3 for all u\in V we have \sum_{f\in\delta(u)}y_{f}\leq 1 . In particular, we accomplish property P1 by adhering to the following rule: after deciding on the value y_{e} assigned to an arriving edge e=uv , we update the cover solution x only at the endpoints of e , i.e. we update only x_{u} and x_{v} . We require the increase of x_{u}+x_{v} to be precisely y_{e} . Thus, we can view it as assigning e a value y_{e} , and after that distributing the value y_{e} to the endpoints of e=uv . Note that we do not always increase both x_{u} and x_{v} ; indeed, x_{u} or x_{v} can even decrease as long as x_{u}+x_{v} is increased by y_{e} . In Section 3.1 , we prove that the values x_{u} , u\in V and y_{e},e\in E are nonnegative, see Lemma 3.4 and Lemma 3.5 below. Note, that nonnegativity of y_{e} , e\in E together with the property P3 implies that y_{e} , e\in E is a feasible fractional matching. Nonnegativity of x_{u} , u\in V together with the property P2 implies that x_{u}/c , u\in V is a feasible fractional cover. Finally, having a feasible fractional cover x_{u}/c , u\in V , and a feasible fractional matching y_{e} , e\in E , the property P1 shows that Algorithm 1 achieves the guarantee c as desired, leading us to the following theorem. Theorem 3.2 . For fractional matchings in the adversarial edge arrival model, Algorithm 1 achieves the guarantee c on graphs of maximum degree three. So, in this work, we show that Algorithm 1 has a guarantee c under both the adversarial edge arrival model and the adversarial vertex arrival model for graphs of maximum degree three. Moreover, Algorithm 1 is optimal for graphs of maximum degree three with respect to both these models, which follows directly from the upper bound in [ 3 ] . 3.1 Nonnegativity of Fractional Matching and Fractional Cover In this section, we show that the values y_{e} , e\in E and x_{u} , u\in V computed by Algorithm 1 are nonnegative. Towards that goal, we need to extend the set of properties that are satisfied by Algorithm 1 . The next lemma contains all additional key properties, and we defer their proof to Appendix B . In the current section, we make use only of the properties P2 , P4 , P6 , and P7 . The analysis of the algorithm requires all of the stated properties, though, and so all of the properties from P1 to P7 are proved together in Appendix B . Lemma 3.3 (Additional Properties) . Let the underlying graph have maximum degree three. At every timepoint the values y and x computed by Algorithm 1 satisfy the following properties: P4 for all u\in V with \text{deg}(u)=2 and \text{type}\left(\delta(u)\right)\notin\left\{(0,2,0),(1,1,0)\right\} we have x_{u}\in\left[2c-1,\frac{5c-2}{2}\right]\quad\text{ and }\quad x_{u}\geq c-1+\sum_{f\in\delta(u)}y_{f}\,, where the first statement can be reformulated as c-x_{u}\in\left[1-\frac{3c}{2},1-c\right] . This property implies that for every spoke e , i.e. for every edge e with \text{type}(e)=2 , we have y_{e}\in\left[1-\frac{3c}{2},1-c\right] due to lines 28 and 29 of Algorithm 1 . P5 for all u\in V the value x_{u} can decrease only upon the arrival of an edge e incident to u such that \text{type}(\delta(u)\setminus\{e\})\in\{(0,2,0),(1,1,0)\} . P6 for all e\in E with \text{type}(e)=1 we have x_{z(e)}\geq\widetilde{y}_{n_{e}+1} and x_{w(e)}\geq c-\widetilde{y}_{n_{e}+1} ; additionally we have x_{w(e)}=c-\widetilde{y}_{n_{e}+1} whenever \text{deg}(w(e))=1 . This property implies that if n_{e} = 1 then we have x_{z(e)}\geq c-\widetilde{y}_{n_{e}+1} , because x_{z(e)}\geq\widetilde{y}_{n_{e}+1} and \widetilde{y}_{n_{e}+1}=\widetilde{y}_{2}=c-\widetilde{y}_{2}=\frac{c}{2} . P7 for all e\in E with \text{type}(e)=2 we have x_{w(e)}\geq y_{e} . Lemma 3.3 guarantees that a certain structure of x is preserved throughout the algorithm. The properties in Lemma 3.3 are also crucial in the construction of y . To illustrate the importance of these properties, consider a scenario when an edge e=uv arrives and before this arrival, we had \deg(z(e))=2 and \text{type}(\delta(z(e)))\notin\{(0,2,0),(1,1,0)\} . In such a scenario, as per Table 1 , we assign e a spoke. Thus, Property P4 ensures that we can assign e a value of c-x_{z(e)} , as in Figure 2 and line 29 in Algorithm 1 , while preserving P3 and while ensuring that y_{e} lies in \left[1-\frac{3c}{2},1-c\right] . Furthermore, as \text{type}(e)=2 and as \deg(z(e))=3 after the arrival of e , Properties P5 and P7 ensure that e remains covered by x in the future. Let us consider a scenario when an arriving edge e gets assigned a path edge and n_{e}>1 . Property P6 ensures that in a consistent instance with ideal value assignments, we have x_{z(e)}\geq c-\widetilde{y}_{n_{e}} , see Figure 2 . In general instances, if feasible with respect to P3 , we assign e the value \widetilde{y}_{n_{e}} ; Otherwise, we assign e the largest possible value that is feasible for P3 . In the latter case, i.e. in the case when e cannot be assigned \widetilde{y}_{n_{e}} , we show that \text{deg}(z(e)) equals three and x_{z(e)} before the arrival of e is sufficiently large to overcome the limitation that the total increase of x_{z(e)}+x_{w(e)} is now smaller than \widetilde{y}_{n_{e}} . The nature of property P6 is to ensure the cover construction of each consistent instance is at least that of the ideal assignment case. Let us state the observation about the value assignments from Section 2.4 . Note that ( 3 ) in Observation 1 follows from ( 7 ) in Lemma A.1 and from ( 2 ) in Observation 1 . Observation 1 . The following properties hold: 1. for all natural n we have \widetilde{y}_{n}\leq c and \widetilde{y}_{n+1}\in\left[\frac{c}{2},\frac{5c-2}{2}\right] . 2. for all natural n we have c-\widetilde{y}_{n+1}\in\left[1-\frac{3c}{2},\frac{c}{2}\right] . 3. for all natural n we have \widetilde{y}_{n+1}+\widetilde{y}_{n}\leq\frac{3c}{2} . Now we are ready to prove that both the values x_{v} , v\in V , and the values y_{f} , f\in E computed by Algorithm 1 are nonnegative at every timepoint. Recall that for each path edge and spoke, we differentiate between its endpoints. In particular, for each e\in E with \text{type}(e)\in\{1,2\} we defined z(e) and w(e) to be as in line 26 of Algorithm 1 . Lemma 3.4 . If the properties P1 , …, P7 hold at every timepoint, then at every timepoint the values x_{v} , v\in V are nonnegative. Proof of Lemma 3.4 . Assume for the sake of a contradiction that there exists v\in V with x_{v}<0 at some timepoint. If there exists f\in\delta(v) with \text{type}(f)=1 then due to P6 we have that either x_{v}\geq\widetilde{y}_{n_{f}+1} or x_{v}\geq c-\widetilde{y}_{n_{f}+1} . Hence by ( 1 ) and ( 2 ) in Observation 1 we have that x_{v}\geq 0 , contradiction. If there exists f\in\delta(v) with \text{type}(f)=2 and z(f)=v then due to the validity P4 (immediately before the edge f arrived) we have that x_{v}\in\left[2c-1,\frac{5c-2}{2}\right] and hence x_{v}>0 contradiction. If there exists f\in\delta(v) with \text{type}(f)=2 and w(f)=v then due to P7 and P4 we have x_{v}\geq y_{f}\geq 1-\frac{3c}{2}\geq 0 , contradiction. Thus, for each f\in\delta(v) we have \text{type}(f)=3 , but by Table 1 this is impossible, a contradiction. ∎ Lemma 3.5 . If the properties P1 , …, P7 hold at every timepoint, then at every timepoint the values y_{f} , f\in E are nonnegative. Proof of Lemma 3.5 . Let f\in E and let us consider three possible types of f . If \text{type}(f)=1 then this type was assigned to f in line 34 , and so by line 33 we have y_{f}=\min\left\{\widetilde{y}_{n_{f}},\,1-\sum_{f_{0}\in\delta(z(f))\setminus\{f\}}y_{f_{0}}\right\}\geq 0\,, where the inequality holds due to P3 . If \text{type}(f)=2 then by P4 we have y_{f}\in\left[1-\frac{3c}{2},1-c\right] hence y_{f}\geq 0 . Finally if \text{type}(f)=3 then upon arrival of f we have \left\{\text{type}(\delta(u)\setminus\{f\})\,\mid\,u\in\text{ends}(f)\right\}\in\mathcal{B\,.} If \{\text{type}(\delta(u)\setminus\{f\})\mid u\in\text{ends}(f)\} is not \{(1,0,0)\} then by assignments in Algorithm 1 we have y_{f}\geq 0 . If \{\text{type}(\delta(u)\setminus\{f\})\mid u\in\text{ends}(f)\} is \{(1,0,0)\} then by line 16 in Algorithm 1 we have y_{f}=\widetilde{y}_{n+1}-(c-\widetilde{y}_{m+1}) for some natural n and m . In this case, by part ( 1 ) in Observation 1 we have \widetilde{y}_{n+1}\geq\frac{c}{2} and by part ( 2 ) in Observation 1 we have (c-\widetilde{y}_{m+1})\leq\frac{c}{2} . Thus in this case we have y_{f}=\widetilde{y}_{n+1}-(c-\widetilde{y}_{m+1})\geq\frac{c}{2}-\frac{c}{2}=0 , and so y_{f}\geq 0 as required. ∎ 3.2 Observations about Algorithm In this section, we collect some observations about Algorithm 1 . Each of these observations is straightforward by itself, and all of them allow us to argue about Algorithm 1 efficiently. The first observation is about general properties for each type of edge: path edges, spokes, and bridges. Observation 2 . The following properties hold: 1. for e\in E with \text{type}(e)=1 , we have that n_{e} is a natural number and y_{e}\leq\widetilde{y}_{n_{e}} . 2. for e\in E with \text{type}(e)=1 , we have that at the moment when e arrives n_{e}=\begin{cases}n_{f}+1&\mbox{ if there exists\hskip 10.22217pt$f\in\delta(z(e))\setminus\{e\},\,\text{type}(f)=1$}\\ 1&\mbox{ otherwise }\\ \end{cases}\,. 3. for e\in E with \text{type}(e)=1 , let us assume e=uv , \text{deg}(v)\leq\text{deg}(u) and let us assume that at the moment when e arrives \text{deg}(v)<3 . Then for \ f\in\delta(v)\setminus\{e\} we have \text{type}(f)=2 or \text{type}(f)=3 at the moment when e arrives. 4. for e\in E with \text{type}(e)=2 , let us assume that after the arrival of e we have \deg(z(e))=3 . Then, after and at the arrival of e the value x_{z(e)} is not changing. 5. for e\in E with \text{type}(e)=3 , we have \deg(u)\geq 2 for all u\in\text{ends}(e) . Parts ( 1 ) and ( 2 ) follow directly from lines 32 and 33 in Algorithm 1 . Part ( 3 ) can be obtained by inspection of the rows and columns corresponding to (1,0,0) in Table 1 . Part ( 4 ) is due to the treatment of spokes in lines from 28 to 30 of Algorithm 1 . Part ( 5 ) can be obtained by inspection of the entries leading to a bridge in Table 1 . The second observation is about vertices in the graph with a specific structure of the edges incident to them. Observation 3 . The following properties hold: 1. for v\in V with \delta(v)\subseteq\{f\,|\,\text{type}(f)=2\} and |\delta(v)|\leq 2 , we have x_{v}=\sum_{f\in\delta(v)}y_{f} . 2. for u\in V with \deg(u)=2 , f_{1},f_{2}\in\delta(u) and \text{type}(f_{1})=\text{type}(f_{2})=1 , we have |n_{f_{1}}-n_{f_{2}}|=1 . Part ( 1 ) follows from line 30 in Algorithm 1 . Part ( 2 ) follows from the rows and columns corresponding to (1,0,0) in Table 1 and the line 32 in Algorithm 1 . Recall that for each path edge and spoke e we differentiate between its endpoints z(e) and w(e) as in line 26 of Algorithm 1 . The next observation is related to the structure of these endpoints. Observation 4 . The following properties hold: 1. for e\in E with \text{type}(e)=1 or \text{type}(e)=2 , we have \text{deg}(z(e))\geq\text{deg}(w(e)) . 2. for e\in E with \text{type}(e)=1 , at the moment when e arrives we have |\{f\in\delta(z)\setminus\{e\}\mid\text{type}(f)=1\}|\leq 1 . 3. for e\in E with \text{type}(e)=1 and n_{e}>2 , there is a unique f\in\delta(z(e))\setminus\{e\} such that \text{type}(f)=1 and z(e)=w(f) . Note that for e\in E with \text{type}(e)=1 and n_{e}=2 , there is an edge f\in\delta(z(e))\setminus\{e\} such that \text{type}(f)=1 and n_{f}=1 , and we have z(e)=w(f) or z(e)=z(f) . Part ( 1 ) is due to the assumption \text{deg}(v)\leq\text{deg}(u) and the definition of z(e) and w(e) in Algorithm 1 . To see part ( 2 ), consider the rows and columns corresponding to (2,0,0) in Table 1 . To see part ( 3 ), consider the edge f that was used to assign a value to n_{e} in line 32 of Algorithm 1 . We have \text{type}(f)=1 and n_{e}=n_{f}+1 and so n_{f}>1 . Assume for a contradiction to ( 3 ) that we have z(f)=z(e) . Due to n_{f}>1 we have that there exists an edge f^{\prime}\in\delta(z(f)) , \text{type}(f^{\prime})=1 and n_{f}=n_{f^{\prime}}+1 , contradicting \text{type}(e)=1 as \text{deg}(z(e))=3 and \text{type}(\delta(z(e))\setminus\{e\})=(2,0,0) . Thus \text{type}(e)=2 by line 27 in Algorithm 1 , contradiction. Note that part ( 2 ) of Observation 4 implies that the parameter n_{e} is well defined for e\in E with \text{type}(e)=1 , i.e. there is only one choice for n_{e} . Finally, we prove the following claim regarding vertices of degree two, which are incident to precisely a path edge and a spoke. In the following, x represents the vertex cover produced by Algorithm 1 . Claim 1 . Assume properties P1 , …, P7 hold, then for all v\in V such that \text{type}(\delta(v))=(1,1,0) with f_{p},f_{s}\in\delta(v) , \text{type}(f_{p})=1 and \text{type}(f_{s})=2 we have that x_{v}=c-\widetilde{y}_{n_{f_{p}}+1}+y_{f_{s}} . Proof of Claim 1 . First as \text{deg}(v)=2 it follows from line 27 that w(f_{s})=v and hence by line 30 f_{s} contributes y_{f_{s}} to x_{v} . If n_{f_{p}}\neq 1 then by ( 1 ) in Observation 4 we have that w(f_{p})=v and hence following line 36 we have that f_{p} contributes c-\widetilde{y}_{n_{f_{p}}+1} to x_{v} as required. If n_{f_{p}}=1 and w(f_{p})=v then f_{p} contributes c-\widetilde{y}_{n_{f_{p}}+1} to x_{v} for the same reasoning as in the case where n_{f_{p}}\neq 1 . If n_{f_{p}}=1 and z(f_{p})=v then by P4 we have that y_{f_{s}}\leq 1-c and hence y_{f_{p}}=\widetilde{y}_{1}=c ; so following line 35 we have that f_{p} contributes y_{f_{p}}-(c-\widetilde{y}_{n_{f_{p}}+1})=\frac{c}{2}=c-\widetilde{y}_{n_{f_{p}}+1} to x_{v} as required. ∎ 3.3 Bridge Assignments In this section, we provide intuition behind the values assigned to bridges and the fractional cover updates for their endpoints in Algorithm 1 . Consider an arriving edge e that is a bridge, so we have \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}\in\mathcal{B} . To provide intuition, we consider each case in \mathcal{B} separately. We use the notation x^{old} to denote the vertex cover before the arrival of e , and x^{new} to denote the vertex cover after the arrival of e and its respective updates. For simplicity, we assume that all edges arrived before e are assigned their ideal values as in consistent instances. Similarly, we further assume that the cover x^{old} satisfies the ideal cover construction depicted in Figure 2 . These assumptions allow us to simplify the exposition; dropping these assumptions requires more nuanced calculations, which we defer to Appendix B . Case 1: \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,0,0)\} Let f_{u}\in\delta(u)\setminus\{e\} and f_{v}\in\delta(v)\setminus\{e\} , thus we have \text{type}(f_{u})=\text{type}(f_{v})=1 , i.e. both are path edges and i\coloneq n_{f_{u}} and j\coloneq n_{f_{v}} . As per our assumptions, we have y_{f_{u}}=\widetilde{y}_{i} and y_{f_{v}}=\widetilde{y}_{j} . First, let us provide the intuition for the value assigned to the edge e . To guarantee the approximation ratio, we ensure \left(x^{new}_{u}-x^{old}_{u}\right)+\left(x^{new}_{v}-x^{old}_{v}\right)=y_{e} as in P1 and x^{new}_{u}+x^{new}_{v}\geq c as in P2 . Therefore, we have to ensure y_{e}+x^{old}_{u}+x^{old}_{v}=y_{e}+(c-\widetilde{y}_{i+1})+(c-\widetilde{y}_{j+1})\geq c\,, after rearranging we obtain y_{e}\geq\widetilde{y}_{i+1}+\widetilde{y}_{j+1}-c . Note that y_{e} is assigned \widetilde{y}_{i+1}+\widetilde{y}_{j+1}-c in line 16 in Algorithm 1 . Intuitively, this is the minimum value we can assign e to ensure P1 and P2 . Now, let us provide the intuition for the assignments x^{new}_{u} and x^{new}_{v} . Without loss of generality, we assume that \widetilde{y}_{i+1}\leq\widetilde{y}_{j+1} , that is for z(e) and w(e) as defined in line 15 in Algorithm 1 we have z(e)=u and w(e)=v . Furthermore, as we are assuming the edge assignments and cover x^{old} followed the values as in consistent instances depicted in Figure 2 , we have x^{old}_{z(e)}=c-\widetilde{y}_{i+1}\qquad\text{and}\qquad x^{old}_{w(e)}=c-\widetilde{y}_{j+1}\,. Since (x^{new}_{u}-x^{old}_{u})+(x^{new}_{v}-x^{old}_{v})=y_{e} , let us explain how to “distribute" y_{e} to get x^{new} from x^{old} . Let us assume y_{e}=a+b where x_{u}^{new}=x_{u}^{old}+a and x^{new}_{v}=x^{old}_{v}+b . For Property P4 to hold we require x^{new}_{u}=x^{old}_{u}+a=c-\widetilde{y}_{i+1}+a\in\left[2c-1,\frac{5c-2}{2}\right]\qquad\text{and}\qquad x^{new}_{v}=x^{old}_{v}+b=c-\widetilde{y}_{j+1}+b\in\left[2c-1,\frac{5c-2}{2}\right] As a=y_{e}-b and y_{e}=\widetilde{y}_{i+1}+\widetilde{y}_{j+1}-c , we have x^{new}_{u}=\widetilde{y}_{j+1}-b . Our strategy is to “balance" x_{u} and x_{v} , i.e. to try to achieve x^{new}_{u}=x^{new}_{v} if possible while preserving P1 - P7 . The property which is a “bottleneck" is Property P4 . On one side, to achieve x^{new}_{u}=x^{new}_{v} we need to have b=\widetilde{y}_{j+1}-\frac{c}{2} and a=\widetilde{y}_{i+1}-\frac{c}{2} ; and so if this assignment is possible we get x^{new}_{u}=x^{new}_{v}=\frac{c}{2} . On the other side, to preserve Property P4 we require x^{new}_{u}=c-\widetilde{y}_{i+1}+a\geq c-1+\widetilde{y}_{i}+y_{e}=\widetilde{y}_{j+1}-(1-\widetilde{y}_{i}-\widetilde{y}_{i+1})\,. Rearranging implies that we need a\geq\widetilde{y}_{i+1}-c+\widetilde{y}_{j+1}-(1-\widetilde{y}_{i}-\widetilde{y}_{i+1})=y_{e}-(1-\widetilde{y}_{i}-\widetilde{y}_{i+1}) . Thus to “balance" x_{u} and x_{v} when possible with respect to Property P4 , we let a=\widetilde{y}_{i+1}-\min\{\frac{c}{2},1-\widetilde{y}_{i}-y_{e}\} as seen in Figure 4 and given in line 17 in Algorithm 1 . Finally, as b=y_{e}-a we also get b=y_{e}-\widetilde{y}_{i+1}+\min\{\frac{c}{2},1-\widetilde{y}_{i}-y_{e}\}=\widetilde{y}_{j+1}-c+\min\{\frac{c}{2},1-\widetilde{y}_{i}-y_{e}\}=\widetilde{y}_{j+1}-\max\{\frac{c}{2},c-(1-\widetilde{y}_{i}-y_{e})\}\,. as seen in Figure 4 and given in line 18 in Algorithm 1 . u v \widetilde{y}_{i} \widetilde{y}_{j} \widetilde{y}_{i+1}-(c-\widetilde{y}_{j+1}) c-\widetilde{y}_{i+1} c-\widetilde{y}_{j+1} \widetilde{y}_{i+1}-\min\{\frac{c}{2}\text{,}\ 1-\widetilde{y}_{i}-y_{e}\} \widetilde{y}_{j+1}-\max\{\frac{c}{2}\text{,}\ c-(1-\widetilde{y}_{i}-y_{e})\} Figure 4: Edge assignment and cover updates upon the arrival of a bridge e with \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,0,0)\} . The dashed cover assignments represent the values of x^{old} under the assumption that prior to the arrival of e , assignments and cover construction are as per Figure 2 . Whereas, the solid cover assignments represent the contribution of e to the updated cover x^{new} . In particular, the value of x^{new}_{u} is the sum of the dashed and solid assignments into u , and the same holds for x^{new}_{v} . Case 2: \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,0,0),(0,1,0)\} Without loss of generality, we can assume that before the arrival of e we had f_{u}\in\delta(u) and f_{v}\in\delta(v) such that \text{type}(f_{u})=1 and \text{type}(f_{v})=2 . Thus as per the assignment of z(e) and w(e) in line 20 of Algorithm 1 , we have z(e)=u and w(e)=v . Let i\coloneq n_{f_{u}} be the position indicator for f_{u} in its respective consistent instance. Furthermore, as stated above, we assume y_{f_{u}}=\widetilde{y}_{i} and y_{f_{v}}=1-\widetilde{y}_{j}-\widetilde{y}_{j+1} for some j . Therefore, as in Figure 2 we have x^{old}_{u}=c-\widetilde{y}_{i+1}\qquad\text{and}\qquad x^{old}_{v}=y_{f_{v}}\,. To guarantee P2 , we need x^{new}_{u}+x^{new}_{v}\geq c and so we require x^{new}_{u}+x^{new}_{v}=y_{e}+x^{old}_{u}+x^{old}_{v}=y_{e}+(c-\widetilde{y}_{i+1})+y_{f_{v}}\geq c\,, leading to y_{e}\geq\widetilde{y}_{i+1}-y_{f_{v}} . Note, that by ( 2 ) in Observation 1 we have y_{f_{v}}\in[1-\frac{3c}{2},\frac{c}{2}] . By Observation 1 we have \widetilde{y}_{i+1}\geq c/2 . Therefore, \max\{\widetilde{y}_{i+1}-y_{f_{v}},0\}=\widetilde{y}_{i+1}-y_{f_{v}} ; and so under the current assumptions, assigning y_{e} the value of \widetilde{y}_{i+1}-y_{f_{v}} is precisely the same as assigning y_{e} the value \max\{\widetilde{y}_{i+1}-y_{f_{v}},0\} in line 21 in Algorithm 1 . Let us now consider how to “distribute" y_{e} to define x^{new} . Let us assume y_{e}=a+b where x^{new}_{u}=x^{old}_{u}+a and x^{new}_{v}=x^{old}_{v}+b . To satisfy Property P4 , we require x^{new}_{u}=c-\widetilde{y}_{i+1}+a\in\left[2c-1,\frac{5c-2}{2}\right]\qquad\text{and}\qquad x^{new}_{v}=y_{f_{v}}+b\in\left[2c-1,\frac{5c-2}{2}\right]\,. Therefore, we require y_{f_{v}}+b\geq 2c-1 , and so b\geq(2c-1)-y_{f_{v}} . To satisfy Property P6 , we require x^{new}_{v}\geq x^{old}_{v} , and so b\geq 0 . Taking the maximum of these lower bounds on b , we get precisely the cover update in line 23 in Algorithm 1 as seen in Figure 5 . So we let b be \max\{(2c-1)-y_{f_{v}},0\} . Now we can retrieve the appropriate value of a since a=y_{e}-b by construction. u v \widetilde{y}_{i} y_{f_{v}} \widetilde{y}_{i+1}-y_{f_{v}} c-\widetilde{y}_{i+1} y_{f_{v}} y_{e}-\max\{(2c-1)-y_{f_{v}}\text{,}\ 0\} \max\{(2c-1)-y_{f_{v}}\text{,}\ 0\} Figure 5: Edge assignment and cover updates upon the arrival of a bridge e with \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,0,0),(0,1,0)\} . The dashed cover assignments represent the values of x^{old} under the assumption that prior to the arrival of e , assignments and cover construction are as per Figure 2 . Whereas, the solid cover assignments represent the contribution of e to the updated cover x^{new} . In particular, the value of x^{new}_{u} is the sum of the dashed and solid assignments into u , and the same holds for x^{new}_{v} . Case 3: \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,0,0),(0,2,0)\} Recall that \text{deg}(v)\leq\text{deg}(u) and so we have \text{type}(\delta(v)\setminus\{e\})=(1,0,0) and \text{type}(\delta(u)\setminus\{e\})=(0,2,0) . Let us assume that f_{v}\in\delta(v)\setminus\{e\} and f_{u}^{1},f_{u}^{2}\in\delta(u)\setminus\{e\} , where \text{type}(f_{v})=1 and \text{type}(f_{u}^{1})=\text{type}(f_{u}^{2})=2 . Let i\coloneq n_{f_{v}} be the position indicator for f_{v} in its respective instance. Furthermore, due to our assumptions we have y_{f_{v}}=\widetilde{y}_{i} , and also by ( 2 ) in Observation 1 we have y_{f_{u}^{1}},y_{f_{u}^{2}}\in[1-\frac{3c}{2},\frac{c}{2}] . So following the cover construction in Figure 2 , we have x^{old}_{u}=y_{f_{u}^{1}}+y_{f_{u}^{2}}\qquad\text{and}\qquad x^{old}_{v}=c-\widetilde{y}_{i+1}. To guarantee P2 , we need x^{new}_{u}+x^{new}_{v}\geq c and so we require x^{new}_{u}+x^{new}_{v}=y_{e}+x^{old}_{u}+x^{old}_{v}=y_{e}+(y_{f_{u}^{1}}+y_{f_{u}^{2}})+(c-\widetilde{y}_{i+1})\geq c\,, leading to y_{e}\geq\widetilde{y}_{i+1}-y_{f_{u}^{1}}-y_{f_{u}^{2}} . Notice that after the arrival of e , the degree of u becomes three, and so no further arriving edges are incident to u . This observation motivates us to keep x_{u} unchanged, i.e. to have x^{new}_{u}=x^{old}_{u} while guaranteeing P2 for f^{1}_{u} and f^{2}_{u} . Since we decide to have x^{new}_{u}=x^{old}_{u} , we “distribute" the whole y_{e} to x_{v} , i.e. we have x^{new}_{v}=x^{old}_{v}+y_{e} . Now, to adhere to Property P4 , we require x^{new}_{v}=x^{old}_{v}+y_{e}=c-\widetilde{y}_{i+1}+y_{e}\in\left[2c-1,\frac{5c-2}{2}\right]\,. Due to our assumptions on y_{f_{u}^{1}} and y_{f_{u}^{2}} , we have c-y_{f_{u}^{1}},c-y_{f_{u}^{2}}\in[2c-1,\frac{5c-2}{2}] by Property P4 . We aim to have x^{new}_{v}=c-y_{f_{u}^{1}} or x^{new}_{v}=c-y_{f_{u}^{2}} , because this would guarantee P4 with respect to x^{new}_{v} . Thus to guarantee P4 , we can select a nonnegative value for y_{e} such that y_{e}\geq\widetilde{y}_{i+1}-\max\{y_{f_{u}^{1}},y_{f_{u}^{2}}\} . That corresponds precisely to the assignment in line 11 in Algorithm 1 . Note that by Observation 1 we have \max\{y_{f_{u}^{1}},y_{f_{u}^{2}}\}\leq\frac{c}{2} and \widetilde{y}_{i+1}\geq c/2 . Hence, we can assign y_{e} precisely \widetilde{y}_{i+1}-\max\{y_{f_{u}^{1}},y_{f_{u}^{2}}\} , because this is a nonnegative value. Now since y_{e}=\widetilde{y}_{i+1}-\max\{y_{f_{u}^{1}},y_{f_{u}^{2}}\} , we have x^{new}_{v}=c-\widetilde{y}_{i+1}+y_{e}=c-\widetilde{y}_{i+1}+\widetilde{y}_{i+1}-\max\{y_{f_{u}^{1}},y_{f_{u}^{2}}\}=c-\max\{y_{f_{u}^{1}},y_{f_{u}^{2}}\} as required. v u \widetilde{y}_{i} y_{f_{u}^{1}} y_{f_{u}^{2}} \widetilde{y}_{i+1}-\max\{y_{f_{u}^{1}}\text{,}\ y_{f_{u}^{2}}\} c-\widetilde{y}_{i+1} y_{f_{u}^{1}} y_{f_{u}^{2}} y_{e} Figure 6: Edge assignment and cover updates upon the arrival of a bridge e with \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,0,0),(0,2,0)\} . The dashed cover assignments represent the values of x^{old} under the assumption that prior to the arrival of e , assignments and cover construction are as per Figure 2 . Whereas, the solid cover assignments represent the contribution of e to the updated cover x^{new} . In particular, the value of x^{new}_{u} is the sum of the dashed and solid assignments into u , and the same holds for x^{new}_{v} . Case 4: \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,1,0),(1,0,0)\} Due to the assumption that \text{deg}(v)\leq\text{deg}(u) we have \text{type}(\delta(v)\setminus\{e\})=(1,0,0) and \text{type}(\delta(u)\setminus\{e\})=(1,1,0) . Let f_{v}\in\delta(v)\setminus\{e\} and f^{1}_{u},f^{2}_{u}\in\delta(u)\setminus\{e\} , that is \text{type}(f^{1}_{u})=\text{type}(f_{v})=1 and \text{type}(f^{2}_{u})=2 . Let i\coloneq n_{f^{1}_{u}} and j\coloneq n_{f_{v}} , thus as stated above we shall assume that y_{f^{1}_{u}}=\widetilde{y}_{i} and y_{f_{v}}=\widetilde{y}_{j} , and by ( 2 ) in Observation 1 y_{f_{u}^{2}}\in[1-\frac{3c}{2},\frac{c}{2}] . Therefore, following the cover construction in Figure 2 , we have x^{old}_{u}=c-\widetilde{y}_{i+1}+y_{f_{u}^{2}}\qquad\text{and}\qquad x^{old}_{v}=c-\widetilde{y}_{j+1} To ensure x^{new}_{u}+x^{new}_{v}\geq c as in P2 , we require x^{new}_{u}+x^{new}_{v}=y_{e}+x^{old}_{u}+x^{old}_{v}=y_{e}+(c-\widetilde{y}_{i+1}+y_{f_{u}^{2}})+(c-\widetilde{y}_{j+1})\geq c\,, leading to y_{e}\geq\widetilde{y}_{j+1}-y_{f_{u}^{2}}-(c-\widetilde{y}_{i+1}) . Notice that after the arrival of e , the degree of u becomes three, and so no further arriving edges are incident to u . As in the previous case, we employ a similar strategy, although this time we no longer have x^{new}_{v}=x^{old}_{v}+y_{e} . Let y_{e}=a+b , where x^{new}_{u}=x^{old}_{u}+a and x^{new}_{v}=x^{old}_{v}+b . If we enforce c-y_{f_{u}^{2}}=x^{new}_{v}=x^{old}_{v}+b=c-\widetilde{y}_{j+1}+b then x^{new}_{v} as in the previous case satisfies Property P4 . Also if we enforce the above equality c-y_{f_{u}^{2}}=c-\widetilde{y}_{j+1}+b then we have b=\widetilde{y}_{j+1}-y_{f_{u}^{2}} , which is nonnegative by our assumptions on y_{f_{u}^{2}} . In a straightforward manner, from b=\widetilde{y}_{j+1}-y_{f_{u}^{2}} and y_{e}=a+b we also get a=y_{e}-b=y_{e}-(\widetilde{y}_{j+1}-y_{f_{u}^{2}}) , as seen in Figure 7 . So we have x^{new}_{u}=x^{old}_{u}+a=c-\widetilde{y}_{i+1}+y_{f_{u}^{2}}+y_{e}-(\widetilde{y}_{j+1}-y_{f_{u}^{2}})=c-\widetilde{y}_{i+1}-\widetilde{y}_{j+1}+2y_{f_{u}^{2}}+y_{e}\,. To ensure that P2 holds for f_{u}^{1} we require x^{new}_{u}\geq c-\widetilde{y}_{i+1} ; similarly, to ensure P2 for f_{u}^{2} we require x^{new}_{u}\geq y_{f_{u}^{2}} because these inequalities are guaranteeing P2 in consistent instances. Therefore we require x^{new}_{u}\geq\max\{c-\widetilde{y}_{i+1},y_{f_{u}^{2}}\} . For this, we need x^{new}_{u}=c-\widetilde{y}_{i+1}-\widetilde{y}_{j+1}+2y_{f_{u}^{2}}+y_{e}\geq\max\{c-\widetilde{y}_{i+1},y_{f_{u}^{2}}\} leading to y_{e}\geq\max\{c-\widetilde{y}_{i+1},y_{f_{u}^{2}}\}+\widetilde{y}_{i+1}+\widetilde{y}_{j+1}-c-2y_{f_{u}^{2}} . Using \max\{c-\widetilde{y}_{i+1},y_{f_{u}^{2}}\}=c-\widetilde{y}_{i+1}+y_{f_{u}^{2}}-\min\{c-\widetilde{y}_{i+1},y_{f_{u}^{2}}\} we get y_{e}\geq c-\widetilde{y}_{i+1}+y_{f_{u}^{2}}-\min\{c-\widetilde{y}_{i+1},y_{f_{u}^{2}}\}+\widetilde{y}_{i+1}+\widetilde{y}_{j+1}-c-2y_{f_{u}^{2}}=\widetilde{y}_{j+1}-y_{f_{u}^{2}}-\min\{c-\widetilde{y}_{i+1},y_{f_{u}^{2}}\} taking the maximum with zero to ensure y_{e}\geq 0 , we get precisely the assignment given in line 6 in Algorithm 1 . v u \widetilde{y}_{j} \widetilde{y}_{i} y_{f_{u}^{2}} \max\{\widetilde{y}_{j+1}-y_{f_{u}^{2}} -\min\{c-\widetilde{y}_{i+1}\text{,}\ y_{f_{u}^{2}}\}\text{,}\ 0\} c-\widetilde{y}_{j+1} c-\widetilde{y}_{i+1} y_{f_{u}^{2}} \widetilde{y}_{j+1}-y_{f_{u}^{2}} y_{e}-(\widetilde{y}_{j+1}-y_{f_{u}^{2}}) Figure 7: Edge assignment and cover updates upon the arrival of a bridge e with \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,1,0),(1,0,0)\} . The dashed cover assignments represent the values of x^{old} under the assumption that prior to the arrival of e , assignments and cover construction are as per Figure 2 . Whereas, the solid cover assignments represent the contribution of e to the updated cover x^{new} . In particular, the value of x^{new}_{u} is the sum of the dashed and solid assignments into u , and the same holds for x^{new}_{v} . 4 Upper Bound for Integral Matchings for Maximum Degree Three In the previous sections, we showed that Algorithm 1 achieves the guarantee c for fractional matchings. In this section, we show that the guarantee c cannot be achieved for integral matchings. In particular, in this section, we prove the following theorem. Theorem 4.1 . For integral matchings in the adversarial edge arrival model, no algorithm achieves a guarantee larger than 0.58065 on graphs of maximum degree three. Let \mathcal{ALG} be a randomized algorithm for integral matchings. Let \gamma be the competitive ratio achievable by \mathcal{ALG} . Consider the following graph in Figure 8 . Here, first edges to arrive are e^{u}_{1} and e^{d}_{1} followed by e^{u}_{2} and e^{d}_{2} . e^{u}_{1} e^{u}_{2} e^{d}_{1} e^{d}_{2} Figure 8: First edges in the considered instances. Let x^{u}_{1} and x^{u}_{2} represent the probability that e^{u}_{1} and e^{u}_{2} are included in the matching by \mathcal{ALG} ; similarly, let x^{d}_{1} and x^{d}_{2} be the probability that e^{d}_{1} and e^{d}_{2} are included in the matching. Due to the symmetry of the constructions in Figures 8 , 10 and 11 , we may assume that x^{d}_{1} equals x^{u}_{1} , and x^{d}_{2} equals x^{u}_{2} . Indeed, for this we could see the process in the following way: first edges to arrive are e^{a}_{1} and e^{b}_{1} followed by e^{a}_{2} and e^{b}_{2} in Figure 9 ; then after \mathcal{ALG} takes decisions related to these four edges, with probability 1/2 we label the edges as x^{u}_{1}:=x^{a}_{1} , x^{d}_{1}:=x^{b}_{1} , x^{u}_{2}:=x^{a}_{2} , x^{d}_{2}:=x^{b}_{2} , and with probability 1/2 we label the edges as x^{u}_{1}:=x^{b}_{1} , x^{d}_{1}:=x^{a}_{1} , x^{u}_{2}:=x^{b}_{2} , x^{d}_{2}:=x^{a}_{2} . Note that the symmetry does not allow us to assume that the inclusion of e^{d}_{1} and the inclusion of e^{u}_{1} in the matching by \mathcal{ALG} are independent events. Let us denote x^{d}_{1} (and so x^{u}_{1} ) by x_{1} , and similarly x^{d}_{2} (and so x^{u}_{2} ) by x_{2} . The constraints on x_{1} , x_{2} and \gamma that we can obtain from Figure 8 are as follows: 2x_{1}\geq 2\gamma and 1-x_{1}-x_{2}\geq 0 . e^{a}_{1} e^{a}_{2} e^{b}_{1} e^{b}_{2} Figure 9: First edges in the constructed instances without “labels”. The first option for the further edge arrivals is depicted in Figure 10 , where after the edges e_{1}^{u} , e_{1}^{d} , e_{2}^{u} , and e_{2}^{d} , all other edges in Figure 10 arrive. In Figure 10 , in the boxes, there are upper bounds on the edges’ probability to be included in the matching by \mathcal{ALG} . Note that if e_{1}^{u} and e_{2}^{u} are included with probabilities x_{1} and x_{2} , respectively, then by integrality of the constructed matching, neither of them is included with the probability 1-x_{1}-x_{2} . An analogous statement holds for e_{1}^{d} , e_{2}^{d} . We obtain a new constraint on x_{1} , x_{2} and \gamma from Figure 8 : 2x_{1}+2x_{2}+4(1-x_{1}-x_{2})\geq 4\gamma . e^{u}_{1} e^{u}_{2} \leq 1-x_{1}-x_{2} \leq 1-x_{1}-x_{2} e^{d}_{1} e^{d}_{2} \leq 1-x_{1}-x_{2} \leq 1-x_{1}-x_{2} Figure 10: First option for the considered instances. The second option for the further edge arrivals is depicted in Figure 11 , where after the edges e_{1}^{u} , e_{1}^{d} , e_{2}^{u} and e_{2}^{d} the remaining edges depicted by solid straight lines arrive; then all curvy edges in Figure 11 arrive; then all dashed edges arrive. Again, in Figure 11 , in the boxes there are either the probabilities or the upper bounds on the edges’ probability to be included in the matching by \mathcal{ALG} . We obtain a new constraint on x_{1} , x_{2} , x_{3}^{u} , x_{3}^{d} , x_{4} and \gamma from Figure 8 : 2x_{1}+2x_{2}+x_{3}^{u}+x_{3}^{d}+x_{4}+(1-x_{1}-x_{3}^{u})+(1-x_{1}-x_{3}^{d})\geq 5\gamma after the arrival of curvy edges; and 2x_{1}+2x_{2}+x_{3}^{u}+x_{3}^{d}+x_{4}+(1-x_{1}-x_{3}^{u})+(1-x_{1}-x_{3}^{d})+(1-x_{3}^{u}-x_{4})+(1-x_{3}^{d}-x_{4})\geq 6\gamma after the arrival of the dashed edge. We also get constraints for each vertex in the graph. e^{u}_{1} e^{u}_{2} x_{3}^{u} e^{d}_{1} e^{d}_{2} x_{3}^{d} 1-x_{1}-x^{u}_{3}\geq 1-x_{1}-x^{d}_{3}\geq x_{4} \leq 1-x^{u}_{3}-x_{4} \leq 1-x^{d}_{3}-x_{4} Figure 11: Second option for the considered instances. Thus, the following Linear Program provides an upper bound on \gamma . \displaystyle\mathmakebox[\widthof{$\underset{\displaystyle}{\mathrm{subject~to}}$}][l]{\underset{\displaystyle}{\mathrm{maximize}}}\quad\gamma \displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{}}{\mathrm{subject~to}}$}][c]{{\mathrm{subject~to}}}\quad \displaystyle 2x_{1}\geq 2\gamma \displaystyle 2x_{1}+2x_{2}+4(1-x_{1}-x_{2})\geq 4\gamma \displaystyle 1-x_{1}-x_{2}\geq 0 \displaystyle 2x_{1}+2x_{2}+x_{3}^{u}+x_{3}^{d}\geq 4\gamma \displaystyle 2x_{1}+2x_{2}+x_{3}^{u}+x_{3}^{d}+x_{4}+(1-x_{1}-x_{3}^{u})+(1-x_{1}-x_{3}^{d})\geq 5\gamma \displaystyle 2x_{1}+2x_{2}+x_{3}^{u}+x_{3}^{d}+x_{4}+(1-x_{1}-x_{3}^{u})+(1-x_{1}-x_{3}^{d}) \displaystyle\qquad+(1-x_{3}^{u}-x_{4})+(1-x_{3}^{d}-x_{4})\geq 6\gamma \displaystyle 1-x_{1}-x_{3}^{u}\geq 0 \displaystyle 1-x_{1}-x_{3}^{d}\geq 0 \displaystyle 1-x_{3}^{u}-x_{4}\geq 0 \displaystyle 1-x_{3}^{d}-x_{4}\geq 0 \displaystyle 0\leq x_{1},\,x_{2},\,x_{3}^{u},\,x_{3}^{d},\,x_{4}\leq 1 Solving the above linear program, we get \gamma\leq 0.58065 as required. 5 Upper Bound for Fractional Matchings for Maximum Degree Four In this section, we show that for fractional matchings, the best possible guarantee deteriorates by going from graphs with maximum degree three to maximum degree four. In particular, we show the following theorem and note that we have 0.58884\widetilde{y}_{2k} . 6. for all natural n we have \widetilde{y}_{n}+2\widetilde{y}_{n+1}<1+\frac{c}{2} . 7. for all natural n we have 1-\widetilde{y}_{n}-\widetilde{y}_{n+1}=c-\widetilde{y}_{n+2} . Note that ( 7 ) in the above lemma is used throughout our work. In particular, we use both 1-\widetilde{y}_{n}-\widetilde{y}_{n+1} and c-\widetilde{y}_{n+2} interchangeably. For the sake of the proof let us provide the first six values of \widetilde{y} , \widetilde{y}_{1}=c\approx 0.5914 , \widetilde{y}_{2}=\frac{c}{2}\approx 0.2957 , \widetilde{y}_{3}=\frac{5c-2}{2}\approx 0.4784 , \widetilde{y}_{4}=4c-2\approx 0.3655 , \widetilde{y}_{5}=\frac{15c-8}{2}\approx 0.4353 , and \widetilde{y}_{6}=\frac{25c}{2}-7\approx 0.3921 . Proof of part ( 1 ) in Lemma A.1 . Let n be a natural number with n\geq 4 , then we have \displaystyle 2(\widetilde{y}_{n+1}-\widetilde{y}_{n}) \displaystyle=3cF_{n+1}+cF_{n-1}-2c-2F_{n+1}+2-3cF_{n}-cF_{n-2} \displaystyle\qquad+2c+2F_{n}-2 \displaystyle=3cF_{n}+3cF_{n-1}+cF_{n-1}-2F_{n}-2F_{n-1}-3cF_{n}-cF_{n-2}+2F_{n} \displaystyle=(4c-2)F_{n-1}-cF_{n-2}\,, where the first equality follows from the definition of \widetilde{y}_{n} , \widetilde{y}_{n+1} , and the second equality follows from the property F_{n}=F_{n-1}+F_{n-2} of the Fibonacci numbers. ∎ Proof of part ( 2 ) in Lemma A.1 . By part ( 1 ) in Lemma A.1 we have \displaystyle 2\widetilde{y}_{n+1} \displaystyle=2\widetilde{y}_{n}+(4c-2)F_{n-1}-cF_{n-2} \displaystyle=2\widetilde{y}_{n}+c(4F_{n-1}-F_{n-2})-2F_{n-1} \displaystyle=2\widetilde{y}_{n}+c(4\frac{\phi^{n-1}-\psi^{n-1}}{\sqrt{5}}-\frac{\phi^{n-2}-\psi^{n-2}}{\sqrt{5}})-2F_{n-1} \displaystyle=2\widetilde{y}_{n}+c(\frac{\phi^{n-1}(4+\psi)-\psi^{n-1}(4+\psi+\sqrt{5})}{\sqrt{5}})-2F_{n-1} \displaystyle=2\widetilde{y}_{n}+c(F_{n-1}(4+\psi)-\psi^{n-1})-2F_{n-1}\qquad\quad(\star) \displaystyle=2\widetilde{y}_{n}-c\psi^{n-1}\qquad\qquad\qquad\qquad\qquad\qquad\quad(\star\star) \displaystyle=2\widetilde{y}_{n}-c(-\frac{1}{\phi})^{n-1} \displaystyle=2\widetilde{y}_{n}-c(-1)^{n-1}\phi^{1-n} \displaystyle=2\widetilde{y}_{n}+c(-1)^{n}\phi^{1-n}\,, where (\star\star) follows from (\star) as 4c+\psi c-2=0 , which is easily verifiable through computation. ∎ Proof of parts ( 3 ) and ( 4 ) in Lemma A.1 . Both statements are corollaries of ( 2 ) in Lemma A.1 . ∎ Proof of part 5 in Lemma A.1 . We consider the following two cases. Case 1: k\leq n \displaystyle 2\widetilde{y}_{2n+1} \displaystyle=2\widetilde{y}_{2n}+c(-1)^{2n}\phi^{1-2n} \displaystyle=2\widetilde{y}_{2n}+c\phi^{1-2n} \displaystyle>2\widetilde{y}_{2n} \displaystyle>2\widetilde{y}_{2k}\,, where the final inequality follows from the fact that k\leq n and by ( 3 ) in Lemma A.1 (\widetilde{y}_{2m})_{m\in\mathbb{N}} is a strictly increasing sequence, hence 2\widetilde{y}_{2n}>2\widetilde{y}_{2k} . Case 2: k>n By ( 4 ) in Lemma A.1 (\widetilde{y}_{2m+1})_{m\in\mathbb{N}} is a strictly decreasing sequence and hence, as k>n we have that 2\widetilde{y}_{2n+1}>2\widetilde{y}_{2k+1} . So, \displaystyle 2\widetilde{y}_{2n+1} \displaystyle>2\widetilde{y}_{2k+1} \displaystyle=2\widetilde{y}_{2k}+c(-1)^{2k}\phi^{1-2k} \displaystyle=2\widetilde{y}_{2k}+c\phi^{1-2k} \displaystyle>2\widetilde{y}_{2k} So, for all natural k and n we have that \widetilde{y}_{2n+1}>\widetilde{y}_{2k} as required. ∎ Proof of part 6 in Lemma A.1 . It is not hard to see that for n\leq 6 the statement holds. So assume n\geq 7 . \displaystyle 2\widetilde{y}_{n}+4\widetilde{y}_{n+1} \displaystyle=2\widetilde{y}_{n}+4\widetilde{y}_{n}+2c(-1)^{n}\phi^{1-n} \displaystyle=6\widetilde{y}_{n}+2c(-1)^{n}\phi^{1-n} \displaystyle\leq 6\widetilde{y}_{n}+2c\phi^{1-n} \displaystyle\leq 6\widetilde{y}_{7}+2c\phi^{1-7} \displaystyle<3\frac{21}{25}+2c(\frac{1+\sqrt{5}}{2})^{-6} \displaystyle<2+c\,, where the second inequality follows from ( 4 ) and ( 5 ) in Lemma A.1 . So it follows that y_{n}\leq y_{7} for all n\geq 7 as required. ∎ Proof of part 7 in Lemma A.1 . We proceed by induction on n . The case where n=1 holds and is easily verifiable. So assume the statement holds for arbitrary natural n that is, 1-\widetilde{y}_{n}-\widetilde{y}_{n+1}+\widetilde{y}_{n+2}=c . So by the inductive hypothesis and ( 2 ) in Lemma A.1 we have, \displaystyle 1- \displaystyle\widetilde{y}_{n+1}-\widetilde{y}_{n+2}+\widetilde{y}_{n+3} \displaystyle=c+\widetilde{y}_{n}-2\widetilde{y}_{n+2}+\widetilde{y}_{n+3} \displaystyle=c+\widetilde{y}_{n}-\widetilde{y}_{n+2}+\frac{1}{2}c(-1)^{n+2}\phi^{-n-1} \displaystyle=c+\widetilde{y}_{n}+\frac{1}{2}c(-1)^{n+2}\phi^{-n-1}-\widetilde{y}_{n+1}-\frac{1}{2}c(-1)^{n+1}\phi^{-n} \displaystyle=c+\frac{1}{2}c(-1)^{n+2}\phi^{-n-1}-\frac{1}{2}c(-1)^{n+1}\phi^{-n}-\frac{1}{2}c(-1)^{n}\phi^{-n+1} \displaystyle=c+\frac{1}{2}c(-1)^{n+2}\phi^{-n-1}+\frac{1}{2}c(-1)^{n+2}\phi^{-n}+\frac{1}{2}c(-1)^{n+1}\phi^{-n+1} \displaystyle=c+\frac{1}{2}c(-1)^{n+1}\phi^{-n-1}(\phi^{2}-\phi-1) \displaystyle=c\,, where the last statement holds as \phi^{2}-\phi-1=0 a well known identity of the golden ratio. ∎ Appendix B Proof of Properties in Main Lemmas Let us now prove both Lemma 3.1 and Lemma 3.3 . We prove the statement by induction on our time point. The base case, i.e. the case when no edge has arrived, can be verified in a straightforward way. Let us assume that the statement, i.e. all properties P1 , …, P7 hold before the arrival of an edge e=uv , where \text{deg}(u)\geq\text{deg}(v) . Let G be the graph after the arrival of e and let x^{old} be produced by the algorithm immediately before the arrival of edge e , i.e. x^{old} and y satisfy P1 , …, P7 with respect to the graph G\setminus e . Let x^{new}_{u} and x^{new}_{v} be the values assigned to x_{u} and x_{v} immediately after the edge e arrived. We now consider the following case study: 1. \text{type}(e)=1 1.i. n_{e}=1 1.ii. n_{e}>1 2. \text{type}(e)=2 3. \text{type}(e)=3 3.i. \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,0,0)\} 3.ii. \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,0,0),(0,1,0)\} 3.iii. \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(0,2,0),(1,0,0)\} 3.iv. \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,1,0),(1,0,0)\} Case 1.1.i. : \text{type}(e)=1 and n_{e}=1 . By line 27 , we have \text{deg}(z(e))<3 or \text{type}(\delta(z(e))\setminus\{e\})\in\{(0,2,0),(1,1,0)\} . Checking P1 . In this case, the assignment of new values x^{new}_{z(e)} , x^{new}_{w(e)} and y_{e} happens in lines 35 , 36 and 33 , so it is straightforward to check that the property P1 holds for G . Checking P2 . Note, that if in line 33 y_{e} is assigned the value \widetilde{y}_{n_{e}} , i.e. the value \widetilde{y}_{1}=c , then the property P2 holds in G , since x^{new}_{z(e)}+x^{new}_{w(e)}=x^{old}_{z(e)}+x^{old}_{w(e)}+y_{e}\geq y_{e}\,. Let us consider the case when y_{e} is assigned the value smaller than \widetilde{y}_{n_{e}} , i.e. c=\widetilde{y}_{1}>1-\sum_{f\in\delta(z(e))\setminus\{e\}}y_{f} . Thus, \text{deg}(z(e))=2 or \text{deg}(z(e))=3 . Due to n_{e}=1 the first entry in \text{type}(\delta(z(e))) equals 1 , and so we have only two possible cases \text{type}(\delta(z(e)))=(1,1,0) and \text{type}(\delta(z(e)))=(1,2,0) by Table 1 . In the case when \text{type}(\delta(z(e)))=(1,1,0) , by property P4 , we have that y_{f}\leq 1-c for f\in\delta(z(e))\setminus\{e\} and thus, y_{e} is assigned the value \widetilde{y}_{n_{1}}=c and P2 holds due to the same arguments as above. In the case when \text{type}(\delta(z(e)))=(1,2,0) , we have \displaystyle x^{new}_{z(e)}=\left(x^{old}_{z(e)}+y_{e}-(c-\widetilde{y}_{2})\right)=x^{old}_{z(e)}+\left(1-\sum_{f\in\delta(z(e)),\,f\neq e}y_{f}\right)-c/2=1-c/2\,, where the first and second equalities are due to assignments in Algorithm 1 and that \widetilde{y}_{2}=c/2 , and the third equality is ( 1 ) in Observation 3 . Similarly, we have \displaystyle x^{new}_{w(e)}=x^{old}_{w(e)}+c/2\,. Thus, we have \displaystyle x^{new}_{z(e)}+x^{new}_{w(e)}=1+x^{old}_{w(e)}\geq c\,. For every f\in\delta(z(e)) , f\neq e we have x^{new}_{z(f)}+x^{new}_{w(f)}=(c-y_{f})+x^{new}_{z(e)}\geq\left(c-(1-c)\right)+1-c/2=3c/2\,, where the first equality holds as w(f)=z(e) and x^{new}_{z(f)}=x_{z(f)}^{old}=c-y_{f} by P5 and line 28 in Algorithm 1 , and the inequality is due to P4 . Since x^{new}_{w(e)}\geq x^{old}_{w(e)} and x^{new}_{a}+x^{new}_{b}\geq c for every ab=f\in\delta(z(e)) , we get that x^{new} satisfies P2 . Checking P4 . The values of x^{new} and x^{old} vary only for z(e) and w(e) . If \text{deg}(z(e))=2 , then by n_{e}=1 we have that \text{type}(\delta(z(e)))=(1,1,0) . Similarly, if \text{deg}(w(e))=2 then by ( 3 ) in Observation 2 and Table 1 , we have \text{type}(\delta(w(e)))=(1,1,0) . Thus, both w(e) and z(e) do not satisfy the premise of P4 , and so P4 continues to hold by the inductive hypothesis. Checking P5 . Here, we follow the same arguments as we used for verifying P2 above. We have x^{new}_{w(e)}=x^{old}_{w(e)}+c/2 , so the value of x_{w(e)} is non-decreasing. We also have that y_{e}=c unless \text{type}(\delta(z(e))\setminus e)=(0,2,0) as shown above when checking P1 ; hence x^{new}_{z(e)}=x^{old}_{z(e)}+c/2 unless \text{type}(\delta(z(e))\setminus e)=(0,2,0) . This shows that P5 holds upon the arrival of e . Checking P6 . Here, we follow the same arguments as we used for verifying P2 above. If y_{e}=c then x^{new}_{z(e)}\geq\frac{c}{2}=\widetilde{y}_{n_{e}+1} . If y_{e}1 . By line 27 , we have \text{deg}(z(e))<3 or \text{type}(\delta(z(e))\setminus\{e\})\in\{(0,2,0),(1,1,0)\} . However, as n_{e}\neq 1 , by line 32 we have that there exists \ f_{p}\in\delta(z)\setminus\{e\} with \text{type}(f_{p})=1 , hence \text{type}(\delta(z(e))\setminus\{e\})\neq(0,2,0) . Moreover, by ( 2 ) in Observation 4 and line 32 in Algorithm 1 we have n_{e}=n_{f_{p}}+1 . Checking P1 . In this case, the assignment of new values x^{new}_{z(e)} , x^{new}_{w(e)} and y_{e} happens in lines 35 , 36 and 33 of Algorithm 1 , so it is straightforward to check that the property P1 holds for G . Checking P2 . Note, that if in line 33 of Algorithm 1 , y_{e} is assigned the value \widetilde{y}_{n_{e}} , then the property P2 holds in G , since x^{new}_{z(e)}+x^{new}_{w(e)}=x^{old}_{z(e)}+x^{old}_{w(e)}+y_{e}\geq c-\widetilde{y}_{n_{e}}+y_{e}=c\,, where the inequality holds as x^{old}_{z(e)}\geq c-\widetilde{y}_{n_{f_{p}}+1}=c-\widetilde{y}_{n_{e}} inductively by P6 on f_{p} and ( 3 ) in Observation 4 . Let us consider the case when y_{e}<\widetilde{y}_{n_{e}} , i.e. \widetilde{y}_{n_{e}}>1-\sum_{f\in\delta(z(e))\setminus\{e\}}y_{f} . Thus, \text{deg}(z(e))=2 or \text{deg}(z(e))=3 . Due to n_{e}>1 the first entry in \text{type}(\delta(z(e))) equals 2 , and so we have only two possible cases \text{type}(\delta(z(e)))=(2,0,0) and \text{type}(\delta(z(e)))=(2,1,0) by Table 1 . In the case when \text{type}(\delta(z(e)))=(2,0,0) , by line 33 in Algorithm 1 we have that for f\in\delta(z(e))\setminus\{e\} , y_{f}\leq\widetilde{y}_{n_{f}}=\widetilde{y}_{n_{e}-1} . So by ( 3 ) in Observation 1 we have that \widetilde{y}_{n_{e}}+\widetilde{y}_{n_{e}-1}<=3c/2<1 thus, we have that y_{e} is assigned the value \widetilde{y}_{n_{e}} ; and so P2 holds due to the same arguments as above. In the case when \text{type}(\delta(z(e)))=(2,1,0) , let f_{s}\in\delta(z(e)) with \text{type}(f_{s})=2 , hence we have \begin{split}x^{new}_{z(e)}&=\left(x^{old}_{z(e)}+y_{e}-(c-\widetilde{y}_{n_{e}+1})\right)\\ &=c-\widetilde{y}_{n_{f_{p}}+1}+y_{f_{s}}+\left(1-\sum_{f\in\delta(z(e)),\,f\neq e}y_{f}\right)-(c-\widetilde{y}_{n_{e}+1})\\ &=1-y_{f_{p}}-\widetilde{y}_{n_{e}}+\widetilde{y}_{n_{e}+1}\\ &\geq 1-\widetilde{y}_{n_{e}-1}-\widetilde{y}_{n_{e}}+\widetilde{y}_{n_{e}+1}\\ &=c\,,\end{split} (1) where the first equality is due to assignments in Algorithm 1 , the second equality is due to Claim 1 , the inequality is due to ( 1 ) in Observation 2 and n_{e}=n_{f_{p}}+1 , and the final equality holds by ( 7 ) in Lemma A.1 . Thus, we have, \displaystyle x^{new}_{z(e)}+x^{new}_{w(e)}\geq c\,. Similarly, we have \displaystyle x^{new}_{w(e)}=x^{old}_{w(e)}+(c-\widetilde{y}_{n_{e}+1})\geq x^{old}_{w(e)}\,, where the inequality holds by ( 1 ) in Observation 1 . So as x^{new}_{z(e)}\geq c and x^{new}_{w(e)}\geq x^{old}_{w(e)} we get that x^{new} satisfies P2 . Checking P4 . The values of x^{new} and x^{old} vary only for z(e) and w(e) . If \text{deg}(z(e)) equals 2 , then by n_{e}>1 we have that \text{type}(\delta(z(e)))=(2,0,0) , hence by the same argument as earlier, by line 33 in Algorithm 1 and ( 3 ) in Observation 1 we have that y_{e}=\widetilde{y}_{n_{e}} . So inductively by P6 and line 35 we have that, x^{new}_{z(e)}=(c-\widetilde{y}_{n_{e}})+\widetilde{y}_{n_{e}}-(c-\widetilde{y}_{n_{e}+1})=\widetilde{y}_{n_{e}+1}\in[\frac{c}{2},\frac{5c-2}{2}]\,, where the inclusion is due to ( 1 ) in Observation 1 , and as \frac{c}{2}>2c-1 we have that P4 holds with respect to z(e) . Moreover, x^{new}_{z(e)}=\widetilde{y}_{n_{e}+1}=c-1+\widetilde{y}_{n_{e}-1}+\widetilde{y}_{n_{e}}\geq c-1+y_{e}+y_{f_{p}}\,, where the second equality holds by ( 7 ) in Lemma A.1 and the inequality holds by ( 1 ) in Observation 2 and as y_{e}=\widetilde{y}_{n_{e}} . Similarly, if \text{deg}(w(e))=2 then by ( 3 ) in Observation 2 and Table 1 , we have \text{type}(\delta(w(e)))=(1,1,0) . Thus, w(e) does not satisfy the premise of P4 , and so P4 continues to hold with respect to w(e) . Checking P5 . Here, we follow the same arguments as we used for verifying P2 above. We have x^{new}_{w(e)}=x^{old}_{w(e)}+(c-\widetilde{y}_{n_{e}+1})\geq x^{old}_{w(e)} , where the inequality holds by ( 1 ) in Observation 1 . So the value of x_{w(e)} is non-decreasing. We also have that y_{e}=\widetilde{y}_{n_{e}} unless \text{type}(\delta(z(e))\setminus e)=(1,1,0) ; hence x^{new}_{z(e)}=x^{old}_{z(e)}+y_{e}-(c-\widetilde{y}_{n_{e}+1})\geq x^{old}_{z(e)} unless \text{type}(\delta(z(e))\setminus e)=(1,1,0) , where the inequality holds by ( 1 ) and ( 2 ) in Observation 1 . This shows that P5 holds upon the arrival of e . Checking P6 . Here, we follow the same arguments as we used for verifying P2 above. If y_{e}=\widetilde{y}_{n_{e}} then inductively by P6 and line 35 we have that x^{new}_{z(e)}\geq(c-\widetilde{y}_{n_{e}})+\widetilde{y}_{n_{e}}-(c-\widetilde{y}_{n_{e}+1})=\widetilde{y}_{n_{e}+1}\,. If y_{e}<\widetilde{y}_{n_{e}} then by ( 1 ) we have x^{new}_{z(e)}\geq c>\widetilde{y}_{n_{e}+1} , where the inequality is due to ( 1 ) in Observation 1 . In all cases, by line 36 we have x^{new}_{w(e)}\geq(c-\widetilde{y}_{n_{e}+1}) which holds with equality if \text{deg}(w(e))=1 . So P6 holds. Checking P7 . Here, we again follow the same arguments as we used for verifying P2 above. We have x^{new}_{w(e)}=x^{old}_{w(e)}+(c-\widetilde{y}_{n_{e}+1}) , so the value of x_{w(e)} is non-decreasing and hence inductively P7 holds with respect to w(e) . Finally, if x^{new}_{z(e)}x^{old}_{w(e)} where the inequality holds as y_{e}\in[1-\frac{3c}{2},1-c] inductively by P4 . So we have that x^{new} satisfies P2 . Checking P4 . First, by line 27 , we have \text{deg}(z(e))=3 so z(e) does not satisfy the premise of P4 . If \text{deg}(w(e))=2 then by Table 1 we have that \text{type}(\delta(w(e)))\in\{(1,1,0),(0,2,0)\} hence w(e) does not satisfy the premise of P4 . So P4 holds inductively. Checking P5 . Similarly to the proof of P2 , we have by line 30 that x^{new}_{z(e)}=x^{old}_{z(e)} and x^{new}_{w(e)}=x^{old}_{w(e)}+y_{e}>x^{old}_{w(e)} , hence P5 holds inductively as all other values of x^{new} remain unchanged. Checking P6 . Following the proof of P5 above, we have that x^{new}_{a}\geq x^{old}_{a} for all a\in V hence, inductively P6 holds with respect to x^{new} . Checking P7 . By line 30 we have that x^{new}_{w(e)}=x^{old}_{w(e)}+y_{e}\geq y_{e} and as all other values of x^{new} remain unchanged we have that P7 holds inductively. Checking P3 . By line 27 we have that \text{type}(\delta(z(e))\setminus\{e\})\notin\{(1,1,0),(0,2,0)\} and \text{deg}_{G\setminus e}(z(e))=2 , so inductively by P4 we have that x^{old}_{z(e)}\geq c-1+\sum_{f\in\delta(z(e))\setminus\{e\}}y_{f} . Therefore, as y_{e}=c-x^{old}_{z(e)} we have that \sum_{f\in\delta(z(e)}y_{f}\leq 1 as required. Now, if \text{deg}(w(e))=3 then \sum_{f\in\delta(w(e))}y_{f}\leq 1 by choice of w(e) in line 26 . If \text{deg}(w(e))=2 then by Table 1 we have that \text{type}(\delta(w))\in\{(1,1,0),(0,2,0)\} so for f\in\delta(z(e))\setminus\{e\} we have inductively by P4 and ( 1 ) in Observation 1 that y_{f}\leq\max\{c,1-c\}=c . Hence, as y_{e}\leq 1-c by P4 , we have that \sum_{f\in\delta(w(e))}y_{f}\leq c+1-c=1 . Finally, if \text{deg}(w(e))=1 then \sum_{f\in\delta(w(e))}y_{f}=y_{e}<1 . So P3 holds with respect to x^{new} as required. Case 3.3.i. : \text{type}(e)=3 and \{\text{type}(\delta(u)\setminus\{e\}),\text{type}(\delta(v)\setminus\{e\})\}=\{(1,0,0)\} . Let f_{u},f_{v},z(e) , and w(e) be defined as in lines 14 and 15 in Algorithm 1 . We first compute the updated values of x^{new}_{z(e)} and x^{new}_{w(e)} . \begin{split}x^{new}_{z(e)}=x^{old}_{z(e)}+\widetilde{y}_{n_{f_{z(e)}}+1}-\min\left\{\frac{c}{2},1-y_{f_{z(e)}}-y_{e}\right\}=c-\min\left\{\frac{c}{2},1-y_{f_{z(e)}}-y_{e}\right\}\,,\end{split} (2) where the first equality is due to line 17 and the second equality holds inductively by P6 as \text{type}(\delta(z(e))\setminus\{e\})=(1,0,0) we have x^{old}_{z(e)}=c-\widetilde{y}_{f_{z(e)}+1} . Similarly, \begin{split}x^{new}_{w(e)}&=x^{old}_{w(e)}+\widetilde{y}_{n_{f_{w(e)}}+1}-\max\left\{\frac{c}{2},c-(1-y_{f_{z(e)}}-y_{e})\right\}\\ &=c-\max\left\{\frac{c}{2},c-(1-y_{f_{z(e)}}-y_{e})\right\}\,,\end{split} (3) where the first equality is due to line 18 and the second equality holds inductively by P6 as \text{type}(\delta(w(e))\setminus\{e\})=(1,0,0) we have x^{old}_{w(e)}=c-\widetilde{y}_{f_{w(e)}+1} . Checking P1 . As \min\{\frac{c}{2},1-y_{f_{z(e)}}-y_{e}\}+\max\{\frac{c}{2},c-(1-y_{f_{z(e)}}-y_{e})\}=c and the assignments the new values x^{new}_{z(e)},x^{new}_{w(e)} , and y_{e} happen in lines 17 , 18 , and 16 , it is straightforward to check that P1 holds for G . Checking P2 . By ( 2 ) and ( 3 ) we have the following, x^{new}_{z(e)}+x^{new}_{w(e)}=2c-\left(\min\left\{\frac{c}{2},1-y_{f_{z(e)}}-y_{e}\right\}+\max\left\{\frac{c}{2},c-(1-y_{f_{z(e)}}-y_{e})\right\}\right)=c\,, where the second equality holds as \min\left\{\frac{c}{2},1-y_{f_{z(e)}}-y_{e}\right\}+\max\left\{\frac{c}{2},c-(1-y_{f_{z(e)}}-y_{e})\right\}=c . We will now show that x^{new}_{z(e)}\geq x^{old}_{z(e)} and x^{new}_{w(e)}\geq x^{old}_{w(e)} which inductively implies that P2 holds with respect to x^{new} . First, by ( 1 ) in Observation 1 we have that \widetilde{y}_{f_{z(e)}+1}\geq\frac{c}{2} , therefore, x^{new}_{z(e)}=x^{old}_{z(e)}+\widetilde{y}_{n_{f_{z(e)}}+1}-\min\left\{\frac{c}{2},1-y_{f_{z(e)}}-y_{e}\right\}\geq x^{old}_{z(e)}\,. Similarly, if \max\left\{\frac{c}{2},c-(1-y_{f_{z(e)}}-y_{e})\right\}=\frac{c}{2} then, x^{new}_{w(e)}=x^{old}_{w(e)}+\widetilde{y}_{n_{f_{w(e)}}+1}-\frac{c}{2}\geq x^{old}_{w(e)}\,. Now, if \max\left\{\frac{c}{2},c-(1-y_{f_{z(e)}}-y_{e})\right\}=c-(1-y_{f_{z(e)}}-y_{e}) then we have, \displaystyle x^{new}_{w(e)} \displaystyle=x^{old}_{w(e)}+\widetilde{y}_{n_{f_{w(e)}}+1}-\left(c-(1-y_{f_{z(e)}}-y_{e})\right)=x^{old}_{w(e)}+1-y_{f_{z(e)}}-\widetilde{y}_{n_{f_{z(e)}}+1} \displaystyle\geq x^{old}_{w(e)}+1-\widetilde{y}_{f_{z(e)}}-\widetilde{y}_{n_{f_{z(e)}}+1}\geq x^{old}_{w(e)}\,, where the second equality is due to line 16 , the first inequality is due to ( 1 ) in Observation 2 , and the final inequality is due to ( 7 ) in Lemma A.1 and ( 2 ) in Observation 1 . So P2 holds with respect to x^{new} as required. Checking P4 . We first show 1-y_{f_{z}}-y_{e}\geq 2-3c as follows, \displaystyle 1-y_{f_{z}}-y_{e}\geq 1-\widetilde{y}_{n_{f_{z(e)}}}-\widetilde{y}_{n_{f_{z(e)}}+1}+(c-\widetilde{y}_{n_{f_{w(e)}}+1})\geq 2(1-\frac{3c}{2})=2-3c\,, where the fist inequality holds by line 16 and ( 1 ) in Observation 2 and the second inequality holds by ( 7 ) in Lemma A.1 and ( 2 ) in Observation 1 . So, by ( 2 ) we have, x_{z}=c-\min\left\{\frac{c}{2},1-y_{f_{z}}-y_{e}\right\}\in[\frac{c}{2},4c-2]\subset[2c-1,\frac{5c-2}{2}]\,. Furthermore, x_{z}=c-\min\left\{\frac{c}{2},1-y_{f_{z}}-y_{e}\right\}\geq c-1+y_{f_{z}}+y_{e}\,. So P4 holds with respect to z(e) . We now check w(e) , first we have, x_{w}=c-\max\left\{\frac{c}{2},c-(1-y_{f_{z}}-y_{e})\right\}\in[2-3c,\frac{c}{2}]\subset[2c-1,\frac{5c-2}{2}]\,, as 1-y_{f_{z}}-y_{e}\geq 2-3c from above. Now, to show x^{new}_{w(e)}\geq c-1+\sum_{f\in\delta(w(e))}y_{f} we consider the following case study. If \max\left\{\frac{c}{2},c-(1-y_{f_{z(e)}}-y_{e})\right\}=\frac{c}{2} then we have the following, \displaystyle c-x^{new}_{w(e)}+y_{e}+y_{f_{w(e)}}\leq 2\widetilde{y}_{n_{f_{w(e)}}+1}+\widetilde{y}_{n_{f_{w(e)}}}-\frac{c}{2}\leq 1 where the first inequality holds as x^{new}_{w(e)}=\frac{c}{2} by ( 3 ) and ( 1 ) in Observation 2 and the second inequality holds by ( 6 ) in Lemma A.1 . We now consider the case where \max\left\{\frac{c}{2},c-(1-y_{f_{z(e)}}-y_{e})\right\}=c-(1-y_{f_{z(e)}}-y_{e}) . First, we have the following, \displaystyle c-(1-y_{f_{z(e)}}-y_{e})\leq\widetilde{y}_{n_{f_{z(e)}}}+\widetilde{y}_{n_{f_{z(e)}}+1}+\widetilde{y}_{n_{f_{w(e)}}+1}-1=\widetilde{y}_{{n_{f_{z}}}+2}+\widetilde{y}_{n_{f_{w}}+1}-c\,, where the inequality is due to line 16 and ( 1 ) in Observation 2 and the equality is due to ( 7 ) in Lemma A.1 . So we have, \displaystyle c-x_{w}+y_{e}+y_{f_{w}} \displaystyle\leq 2\widetilde{y}_{n_{f_{w}}+1}+\widetilde{y}_{n_{f_{w}}}+\widetilde{y}_{{n_{f_{z}}}+2}+\widetilde{y}_{{n_{f_{z}}}+1}-2c \displaystyle\leq 1+\frac{c}{2}+\frac{3c}{2}-2c=1\,, where the first inequality holds by line 16 and as c-x_{w(e)}=c-(1-y_{f_{z(e)}}-y_{e})\leq\widetilde{y}_{{n_{f_{z}}}+2}+\widetilde{y}_{n_{f_{w}}+1}-c by ( 3 ) and the second inequality holds by ( 6 ) in Lemma A.1 and because \widetilde{y}_{{n_{f_{z}}}+2}+\widetilde{y}_{{n_{f_{z}}}+1}\leq\frac{3c}{2} which follows from ( 7 ) in Lemma A.1 as well as ( 2 ) in Observation 1 . So P4 holds with respect to w(e) and therefore with respect to G as required. Checking P5 , P6 , and P7 . Following the proof of P2 above we have shown that both x^{new}_{z(e)}\geq x^{old}_{z(e)} and x^{new}_{w(e)}\geq x^{old}_{w(e)} and so as all other values of x remain unchanged we have that properties P5 , P6 , and P7 hold inductively. Checking P3 . Following the proof of P4 above we have that x^{new}_{z(e)}\geq c-1+\sum_{f\in\delta(z(e))}y_{f} , x^{new}_{w(e)}\geq c-1+\sum_{f\in\delta(w(e))}y_{f} , and x^{new}_{z(e)},x^{new}_{w(e)}\leq\frac{5c-2}{2}2c-1$}\\ 2c-1&\mbox{ if $y_{f_{2}}\leq 2c-1$}\\ \end{cases}\end{split} (5) where the first equality is due to line 23 and the second equality follows from ( 1 ) in Observation 3 . Checking P1 . In this case, the assignment of new values x^{new}_{z(e)} , x^{new}_{w(e)} and y_{e} happen in lines 21 , 22 , and 23 , so it is straightforward to check that the property P1 holds for G . Checking P2 . By ( 4 ) and ( 5 ) we have, \displaystyle x^{new}_{z(e)}+x^{new}_{w(e)}=c-\widetilde{y}_{n_{f_{1}}+1}+\max\left\{\widetilde{y}_{n_{f_{1}}+1}-y_{f_{2}},0\right\}+y_{f_{2}}\geq c\,, where the inequality follows directly from the previous line through a case analysis of \max\left\{\widetilde{y}_{n_{f_{1}}+1}-y_{f_{2}},0\right\} . We proceed by showing that x^{new}_{z(e)}\geq x^{old}_{z(e)} and x^{new}_{w(e)}\geq x^{old}_{w(e)} which will imply inductively that P2 hols on G . First, let us consider x^{new}_{z(e)} . By ( 4 ) it suffices to show that y_{e}-\max\left\{(2c-1)-y_{f_{2}},0\right\}\geq 0 . Consider the following, \displaystyle y_{e}-\max\left\{(2c-1)-y_{f_{2}},0\right\} \displaystyle=\max\left\{\widetilde{y}_{n_{f_{1}}+1}-y_{f_{2}},0\right\}-\max\left\{(2c-1)-y_{f_{2}},0\right\} \displaystyle\geq\begin{cases}\widetilde{y}_{n_{f_{1}}+1}-(2c-1)&\mbox{ if $y_{e}=\widetilde{y}_{n_{f_{1}}+1}-y_{f_{2}}$}\\ 0&\mbox{ if $y_{e}=0$}\\ \end{cases}\,, where the equality is due to line 21 and the inequality holds as if y_{e}=0 then y_{f_{2}}\geq\widetilde{y}_{n_{f_{1}}+1}\geq\frac{c}{2}>2c-1 by ( 1 ) in Observation 1 and so \max\left\{(2c-1)-y_{f_{2}},0\right\}=0 . So x^{new}_{z(e)}\geq x^{old}_{z(e)} ; moreover, by ( 5 ) we have that x^{new}_{w(e)}\geq x^{old}_{w(e)} hence P2 holds as required. Checking P4 . We first show x^{new}_{z(e)}\in[2c-1,\frac{5c-2}{2}] . By 4 we have, x^{new}_{z(e)}=\begin{cases}c-\widetilde{y}_{n_{f_{1}}+1}&\mbox{ if $y_{f_{2}}\geq\widetilde{y}_{n_{f_{1}}+1}$ }\\ c-y_{f_{2}}&\mbox{ if $y_{f_{2}}\in[2c-1,\widetilde{y}_{n_{f_{1}}+1})$}\\ 1-c&\mbox{ if $y_{f_{2}}<2c-1$}\\ \end{cases}\ \ \in[2c-1,\frac{5c-2}{2}]\,, where the inclusion holds as 2c-1<1-c<\frac{5c-2}{2} , \widetilde{y}_{n_{f_{1}}+1}\in[\frac{c}{2},\frac{5c-2}{2}] by ( 1 ) in Observation 1 , and y_{f_{2}}\in[1-\frac{3c}{2},1-c] inductively by P4 , so if y_{f_{2}}\geq\widetilde{y}_{n_{f_{1}}+1} then \widetilde{y}_{n_{f_{1}}+1}\leq 1-c hence, c-\widetilde{y}_{n_{f_{1}}+1}\in[2c-1\frac{c}{2}] . We will now show that x^{new}_{z(e)}\geq c-1+\sum_{f\in\delta(z(e))}y_{f} through a case analysis on the value of x^{new}_{z(e)} as in ( 4 ). If x^{new}_{z(e)}=c-\widetilde{y}_{n_{f_{1}}+1} then we have that y_{f_{2}}\geq\widetilde{y}_{n_{f_{1}}+1} and hence by line 21 we have that y_{e}=0 so, c-x^{new}_{z(e)}+y_{f_{1}}+y_{e}=\widetilde{y}_{n_{f_{1}}+1}+y_{f_{1}}\leq\widetilde{y}_{n_{f_{1}}+1}+\widetilde{y}_{n_{f_{1}}}\leq 1\,, where the first inequality follows from ( 1 ) in Observation 2 and the second inequality is due to ( 3 ) in Observation 1 . If x^{new}_{z(e)}=c-y_{f_{2}} then we have that y_{f_{2}}\in[2c-1,\widetilde{y}_{n_{f_{1}}+1}) and hence by line 21 y_{e}=\widetilde{y}_{n_{f_{1}}+1}-y_{f_{2}} . So, c-x^{new}_{z(e)}+y_{f_{1}}+y_{e}=\widetilde{y}_{n_{f_{1}}+1}+y_{f_{1}}\leq\widetilde{y}_{n_{f_{1}}+1}+\widetilde{y}_{n_{f_{1}}}\leq 1\,, where the inequalities hold for the same reason as in the case where x^{new}_{z(e)}=c-\widetilde{y}_{n_{f_{1}}+1} . Finally, if x^{new}_{z(e)}=1-c then we have that y_{f_{2}}<2c-1<\widetilde{y}_{n_{f_{1}}+1} and hence by line 21 we have y_{e}=\widetilde{y}_{n_{f_{1}}+1}-y_{f_{2}} so, c-x^{new}_{z(e)}+y_{f_{1}}+y_{e}\leq\widetilde{y}_{n_{f_{1}}+1}+\widetilde{y}_{n_{f_{1}}}+2c-1-y_{f_{2}}\leq 5c-2<1\,, where the first inequality is due to ( 1 ) in Observation 2 and the second inequality holds as \widetilde{y}_{n_{f_{1}}+1}+\widetilde{y}_{n_{f_{1}}}\leq\frac{3c}{2} by ( 3 ) in Observation 1 and y_{f_{2}}\geq 1-\frac{3c}{2} inductively by P4 . So P4 holds with respect to z(e) . We now check w(e) , by ( 5 ) we have that, x^{new}_{w(e)}=\begin{cases}y_{f_{2}}&\mbox{ if $y_{f_{2}}>2c-1$}\\ 2c-1&\mbox{ if $y_{f_{2}}\leq 2c-1$}\\ \end{cases}\ \ \in[2c-1,\frac{5c-2}{2}]\,, where the inclusion holds as y_{f_{2}}\leq 1-c inductively by P4 . We will now show that x^{new}_{w(e)}\geq c-1+\sum_{f\in\delta(w(e))}y_{f} through a case analysis on the value of x^{new}_{w(e)} as in ( 4 ). If x^{new}_{w(e)}=y_{f_{2}} we have that y_{f_{2}}>2c-1 and hence, c-x^{new}_{w(e)}+y_{f_{2}}+y_{e}=c-y_{e}<1\,. Moreover, if x^{new}_{w(e)}=2c-1 then y_{f_{2}}<2c-1<\widetilde{y}_{n_{f_{1}}+1} and hence by line 21 we have y_{e}=\widetilde{y}_{n_{f_{1}}+1}-y_{f_{2}} so, c-x^{new}_{w(e)}+y_{f_{2}}+y_{e}=1-c+\widetilde{y}_{n_{f_{1}}+1}\leq 1\,, where the inequality holds by ( 1 ) in Observation 1 . So P4 holds with respect to w(e) and hence on G inductively. Checking P5 , P6 , and P7 . Following the proof of P2 above we have shown that both x^{new}_{z(e)}\geq x^{old}_{z(e)} and x^{new}_{w(e)}\geq x^{old}_{w(e)} and so as all other values of x remain unchanged we have that properties P5 , P6 , and P7 hold inductively. Checking P3 . Following the proof of P4 we have that x^{new}_{z(e)}\geq c-1+\sum_{f\in\delta(z(e))}y_{f} , x^{new}_{w(e)}\geq c-1+\sum_{f\in\delta(w(e))}y_{f} , and x^{new}_{z(e)},x^{new}_{w(e)}\leq\frac{5c-2}{2}\widetilde{y}_{n_{f_{v}}+1}$}\\ c-y_{f_{1}}&\mbox{ if $y_{f_{2}}\leq y_{f_{1}}\leq\widetilde{y}_{n_{f_{v}}+1}$}\\ \end{cases}\end{split} (7) where the second equality holds by line 11 and inductively by P6 as \text{type}(\delta(v)\setminus\{e\})=(1,0,0) . Checking P1 . In this case, the assignment of new values x^{new}_{u} , x^{new}_{v} and y_{e} happens in lines 11 and 12 , so it is straightforward to check that the property P1 holds for G . Checking P2 . By ( 6 ) and ( 7 ) we have, x^{new}_{u}+x^{new}_{v}=c-\widetilde{y}_{n_{f_{v}}+1}+\max\left\{\widetilde{y}_{n_{f_{v}}+1}-y_{f_{1}},0\right\}+y_{f_{1}}+y_{f_{2}}\geq c where the inequality holds by a case analysis of \max\left\{\widetilde{y}_{n_{f_{v}}+1}-y_{f_{1}},0\right\} . Moreover, by ( 6 ) and ( 7 ) we have, that x^{new}_{u}=x^{old}_{u} and x^{new}_{v}=x^{old}_{v}+y_{e}=x^{old}_{v}+\max\left\{\widetilde{y}_{n_{f_{v}}+1}-y_{f_{1}},0\right\}\geq x^{old}_{v} , therefore we have inductively that P2 holds for G as required. Checking P4 . First, as \text{deg}(u)=3 we have that u does not satisfy the premise of P4 . Now, by ( 7 ) we have that, x^{new}_{v}=\begin{cases}c-\widetilde{y}_{n_{f_{v}}+1}&\mbox{ if $y_{f_{1}}>\widetilde{y}_{n_{f_{v}}+1}$}\\ c-y_{f_{1}}&\mbox{ if $y_{f_{2}}\leq y_{f_{1}}\leq\widetilde{y}_{n_{f_{v}}+1}$}\\ \end{cases} and hence we proceed by case analysis on the value of x^{new}_{v} . If x^{new}_{v}=c-\widetilde{y}_{n_{f_{v}}+1} then y_{f_{1}}>\widetilde{y}_{n_{f_{v}}+1} and hence by line 11 we have that y_{e}=0 . Moreover, inductively by P4 we have y_{f_{1}}\leq 1-c and so x^{new}_{v}=c-\widetilde{y}_{n_{f_{v}}+1}\geq 2c-1 and hence by ( 2 ) in Observation 1 we have that x^{new}_{v}\in[2c-1,\frac{c}{2}]\subset[2c-1,\frac{5c-2}{2}] . Also, c-x^{new}_{v}+y_{e}+y_{f_{v}}=\widetilde{y}_{n_{f_{v}}+1}+y_{f_{v}}\leq\widetilde{y}_{n_{f_{v}}+1}+\widetilde{y}_{n_{f_{v}}}\leq 1\, where the first inequality holds by ( 1 ) in Observation 2 and the second holds by ( 3 ) in Observation 1 . If x^{new}_{v}=c-y_{f_{1}} then y_{f_{1}}\leq\widetilde{y}_{n_{f_{v}}+1} and hence by line 11 we have that y_{e}=\widetilde{y}_{n_{f_{v}}+1}-y_{f_{1}} . Moreover, inductively by P4 we have that y_{f_{1}}\in[1-\frac{3c}{2},1-c] and so, x^{new}_{v}=c-y_{f_{1}}\in[2c-1,\frac{5c-2}{2}] . Also, c-x^{new}_{v}+y_{e}+y_{f_{v}}=\widetilde{y}_{n_{f_{v}}+1}+y_{f_{v}}\leq\widetilde{y}_{n_{f_{v}}+1}+\widetilde{y}_{n_{f_{v}}}\leq 1\, where the first inequality holds by ( 1 ) in Observation 2 and the second holds by ( 3 ) in Observation 1 . So P4 holds as required. Checking P5 , P6 , and P7 . Following the proof of P2 above we have shown that both x^{new}_{u}\geq x^{old}_{u} and x^{new}_{v}\geq x^{old}_{v} and so as all other values of x remain unchanged we have that properties P5 , P6 , and P7 hold inductively. Checking P3 . Following the proof of P4 we have that x^{new}_{v}\geq c-1+\sum_{f\in\delta(v)}y_{f} and x^{new}_{v}\leq\frac{5c-2}{2}\widetilde{y}_{n_{f_{v}}+1}-y_{f_{2}}$}\\ c-\widetilde{y}_{n_{f_{1}}+1}+y_{f_{2}}-(\widetilde{y}_{n_{f_{v}}+1}-y_{f_{2}})&\mbox{ if $y_{e}=0\leq\widetilde{y}_{n_{f_{v}}+1}-y_{f_{2}}$}\\ \end{cases}\\ &\geq c-\widetilde{y}_{n_{f_{1}}+1}+y_{f_{2}}-\min\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\}\\ &=\max\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\}\end{split} (8) where the second equality holds by line 6 and as x^{old}_{u}=c-\widetilde{y}_{n_{f_{1}}+1}+y_{f_{2}} by Claim 1 and the third equality holds from a case analysis of the two max functions. The inequality holds as if y_{e}=0 then \widetilde{y}_{n_{f_{v}}+1}-y_{f_{2}}\leq\min\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\} and the final equality is due to a case analysis of \min\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\} . Moreover, by line 8 we have, \begin{split}x^{new}_{v}&=x^{old}_{v}+\max\left\{\widetilde{y}_{n_{f_{v}}+1}-y_{f_{2}},0\right\}=\max\left\{c-\widetilde{y}_{n_{f_{v}}+1},c-y_{f_{2}}\right\}\end{split} (9) where the second equality holds as x^{old}_{v}=c-\widetilde{y}_{n_{f_{v}}+1} inductively by P6 and by a case analysis of \max\left\{\widetilde{y}_{n_{f_{v}}+1}-y_{f_{2}},0\right\} . Checking P1 . In this case, the assignment of new values x^{new}_{u} , x^{new}_{v} and y_{e} happens in lines 6 , 7 and 8 , so it is straightforward to check that the property P1 holds for G . Checking P2 . Following ( 8 ) and ( 9 ) we have that, x^{new}_{u}+x^{new}_{v}\geq\max\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\}+\max\left\{c-\widetilde{y}_{n_{f_{v}}+1},c-y_{f_{2}}\right\}\geq y_{f_{2}}+c-y_{f_{2}}=c Furthermore, by ( 8 ) we have that x^{new}_{u}\geq\max\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\} so inductively by P6 we have that \sum_{a\in\text{ends}(f_{1})}x^{new}_{a}\geq\widetilde{y}_{n_{f_{1}}+1}+c-\widetilde{y}_{n_{f_{1}}+1}=c also, as x^{new}_{u}\geq y_{f_{2}} it follows by ( 4 ) in Observation 2 that \sum_{a\in\text{ends}(f_{2})}x^{new}_{a}\geq c . Furthermore, by ( 9 ) we have that x^{new}_{v}\geq x^{old}_{v} and hence we have inductively that P2 holds. Checking P4 . First we have that as \text{deg}(u)=3 that u fails the premise of P4 . Now, following ( 9 ) we have that, \displaystyle x^{new}_{v}=\max\left\{c-\widetilde{y}_{n_{f_{v}}+1},c-y_{f_{2}}\right\}\in[2c-1,\frac{5c-2}{2}] where the inclusion holds as if x^{new}_{v}=c-\widetilde{y}_{n_{f_{v}}+1} then \widetilde{y}_{n_{f_{v}}+1}\leq y_{f_{2}}\leq 1-c inductively by P4 so along with ( 2 ) in Observation 1 we have that x^{new}_{v}\in[2c-1,\frac{c}{2}]\subset[2c-1,\frac{5c-2}{2}] . Moreover, if x^{new}_{v}=c-y_{f_{2}} then inductively by P4 we have that x^{new}_{v}\in[2c-1,\frac{5c-2}{2}] . To show x^{new}_{v}\geq c-1+\sum_{f\in\delta(v)}y_{f} we consider the following case study based on the value of x^{new}_{v} as in ( 9 ). If x^{new}_{v}=c-\widetilde{y}_{n_{f_{v}}+1} then we have that \widetilde{y}_{n_{f_{v}}+1}\leq y_{f_{2}} hence y_{e}=0 therefore, c-x^{new}_{v}+y_{f_{v}}+y_{e}\leq\widetilde{y}_{n_{f_{v}}+1}+\widetilde{y}_{n_{f_{v}}}<1\,, where the first inequality follows from ( 1 ) in Observation 2 and the second inequality follows from ( 3 ) in Observation 1 . If x^{new}_{v}=c-y_{f_{2}} then, \displaystyle c-x^{new}_{v}+y_{f_{v}}+y_{e} \displaystyle=y_{f_{2}}+y_{f_{v}}+\max\{\widetilde{y}_{n_{f_{v}}+1}-y_{f_{2}}-\min\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\},0\} \displaystyle=\begin{cases}y_{f_{2}}+y_{f_{v}}&\mbox{ if $y_{e}=0$}\\ \widetilde{y}_{n_{f_{v}}+1}+y_{f_{v}}-\min\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\}&\mbox{ if $y_{e}\neq 0$}\end{cases} \displaystyle\leq 1 where the first equality holds by the assignment of y_{e} in line 6 and the inequality holds as y_{f_{2}}\leq 1-c inductively by P4 and y_{f_{v}}\leq c by ( 1 ) in Observation 1 so y_{f_{2}}+y_{f_{v}}\leq 1-c+c=1 and by ( 1 ) in Observation 2 and ( 3 ) in Observation 1 we have that \widetilde{y}_{n_{f_{v}}+1}+y_{f_{v}}\leq\widetilde{y}_{n_{f_{v}}+1}+\widetilde{y}_{n_{f_{v}}}<1 . So P4 holds on G as required. Checking P5 . As \text{type}(\delta(u)\setminus\{e\})=(1,1,0) we have that the premise of P5 does not hold with respect to u . Moreover, by ( 9 ) we have that x^{new}_{v}\geq x^{old}_{v} as required. Checking P6 and P7 . By ( 8 ) and ( 9 ) we have that x^{new}_{u}\geq\max\left\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\right\} and x^{new}_{v}\geq x^{old}_{v} and so both P6 and P7 holds. Checking P3 . Following the proof of P4 we have that x^{new}_{v}\geq c-1+\sum_{f\in\delta(v)}y_{f} and x^{new}_{v}\leq\frac{5c-2}{2}<1 and hence, \sum_{f\in\delta(v)}y_{f}\leq 1 as required. To show \sum_{f\in\delta(u)}y_{f}\leq 1 , we consider a case study on the value of y_{e} as in line 6 . If y_{e}=0 then, \sum_{f\in\delta(u)}y_{f}=y_{f_{1}}+y_{f_{2}}\leq c+1-c=1\,, where the inequality holds by ( 1 ) in Observation 1 and inductively by P4 . If we have y_{e}=\widetilde{y}_{n_{f_{v}}+1}-y_{f_{2}}-\min\left\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\right\} then we have \displaystyle\sum_{f\in\delta(u)}y_{f} \displaystyle=y_{f_{1}}+y_{f_{2}}+\widetilde{y}_{n_{f_{v}}+1}-y_{f_{2}}-\min\left\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\right\} \displaystyle\leq\widetilde{y}_{n_{f_{1}}}+\widetilde{y}_{n_{f_{v}}+1}-\min\left\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\right\} \displaystyle\leq c+\frac{5c-2}{2}-(1-\frac{3c}{2})=5c-2<1 where the first inequality holds by ( 1 ) in Observation 2 . The second inequality holds as \widetilde{y}_{n_{f_{1}}}\leq c and \widetilde{y}_{n_{f_{v}}+1}\leq\frac{5c-2}{2} by ( 1 ) in Observation 1 and \min\left\{c-\widetilde{y}_{n_{f_{1}}+1},y_{f_{2}}\right\}\geq 1-\frac{3c}{2} by ( 2 ) in Observation 1 and inductively by P4 . So P3 holds as required. So all the properties hold by induction. Appendix C Upper Bound for MinIndex for Maximum Degree Three First, let us introduce a framework developed by Buchbinder, Segev, and Tkach [ 3 ] , so-called MinIndex algorithm. This framework produces an integral matching within the general adversarial edge arrivals model. MinIndex is parametrized by a natural number k and k nonnegative numbers p_{1} , …, p_{k} such that p_{1}+\ldots+p_{k}=1 . The framework functions by maintaining a distribution of matchings where each matching in this distribution is returned with a pre-determined probability. Once an edge arrives, it is greedily added to the first matching for which it is feasible, see Algorithm 2 . Algorithm 2 MinIndex( k,p_{1},\dots,p_{k} ) Initialize: M_{i}\leftarrow\emptyset for all i=1,\dots,k When e arrives: if M_{i}\cup\{e\} is not feasible for all i=1,\dots,k then Reject e . else M_{i}\leftarrow M_{i}\cup\{e\} where i is the minimal index for which M_{i}\cup\{e\} is feasible. end if return M_{i} with probability p_{i} . [ 3 ] shows that MinIndex with k=3 and (p_{1},p_{2},p_{3})=(5/9,3/9,1/9) achieves the guarantee 5/9 in the adversarial edge arrival model when the underlying graph is restricted to be a forest. Here, we show that 5/9 is the best guarantee achievable by MinIndex even on forests with maximum degree three. Note, [ 3 ] demonstrated that MinIndex cannot achieve a guarantee larger than 5/9 on forests of maximum degree four, so our results improves this bound both in terms of the guarantee and in terms of the permitted maximum degree. Theorem C.1 . For no selection of parameters k and p_{1} , p_{2} , … p_{k} , MinIndex achieves a guarantee larger than 5/9 on forests of maximum degree three. In the remaining part of this appendix, we prove Theorem C.1 . For this, we consider two families of instances. The first family is constructed below. The second family is constructed based on consistent instances from Section 2.1 but with a modified edge arrival order. The instances in both families are parametrized by a parameter n . Let k be a natural number and p_{1} , …, p_{k} be nonnegative numbers such that p_{1}+p_{2}+\ldots+p_{k}=1 . Let M_{1} , …, M_{k} be the matchings computed by MinIndex, i.e. by Algorithm 2 . Let M be a random variable indicating the matching output by Algorithm 2 . We denote by \gamma the guarantee achieved by MinIndex with the parameters k and p_{1} , …, p_{k} . First Family Let n be a natural number. Let us describe the edges that are going to arrive at the beginning. The first edges to arrive form a path P , consisting of the edges e_{1} , e_{2} ,…, e_{3n+3} . Here, the edges e_{j} and e_{j+1} are incident for every j=1,\ldots,3n+2 . The first three batches to arrive are as follows: • B_{1}:=\{e_{i}\mid i\equiv 2\mod 3\}=\{e_{2},e_{5},e_{8},\ldots,e_{3n+2}\} • B_{2}:=\{e_{i}\mid i\equiv 1\mod 3\}\,\cup\,\{e_{3n+3)}\}=\{e_{1},e_{4},e_{7},\ldots,e_{3n+1}\}\,\cup\,\{e_{3n+3}\} • B_{3}:=\{e_{i}\mid i\equiv 0\mod 3,\,i\leq 3n\}=\{e_{3},e_{6},e_{9},\dots,e_{3n}\} . Let us describe the batches B_{4} , B_{5} , B_{6} , B_{7} . Let us first describe the structure of the edges in these batches. For this, we iterate over the vertices u on the path P which are not incident to e_{1} nor to e_{2n+3} . For each such vertex u we construct the following edges: • if \delta(u) has no edges in B_{3} then we construct an edge uw^{u} and place it in B_{6} • if \delta(u) has no edges in B_{1} then we construct edges uw^{u} , w^{u}v^{u} , v^{u}t^{u} and place them in B_{7} , B_{4} and B_{5} , respectively • if \delta(u) has no edges in B_{2} then we construct edges uw^{u} , w^{u}v^{u} , v^{u}t^{u} , t^{u}r^{u} , v^{u}q^{u} and place them in B_{7} , B_{5} , B_{4} , B_{5} , B_{6} , respectively. An example of the underlying graph for the case n=2 is shown in Figure 13 . It is straightforward to verify that with this arrival order, we have M_{1}=B_{1}\cup B_{4} , M_{2}=B_{2}\cup B_{5} , M_{3}=B_{1}\cup B_{6} , and M_{4}=B_{7} as in Figure 13 . It is also straightforward to verify that the constructed graph always has a perfect matching, showing thus that the cardinality of a maximum matching equals 6n+2 . M_{2} M_{1} M_{3} M_{2} M_{1} M_{3} M_{4} M_{2} M_{1} M_{2} M_{3} M_{4} M_{1} M_{2} M_{3} M_{2} M_{1} M_{2} M_{4} M_{2} M_{1} M_{2} M_{3} M_{4} M_{1} M_{2} M_{3} Figure 13: The instance from the first family for n=2 . Moreover, the expected cardinality of the matching produced by Algorithm 2 is as follows, \mathbb{E}[|M|]=\sum_{i=1}^{k}|M_{i}|p_{i}=(3n+1)p_{1}+(4n+2)p_{2}+3np_{3}+2np_{4} So we get the following constraint on the competitiveness c of MinIndex 2 , \gamma\leq\frac{\mathbb{E}[|M|]}{6n+2}=\frac{3n+1}{6n+2}p_{1}+\frac{4n+2}{6n+2}p_{2}+\frac{3n}{6n+2}p_{3}+\frac{2n}{6n+2}p_{4}\,, taking the limit as n\rightarrow\infty we get, \gamma\leq\frac{1}{2}p_{1}+\frac{2}{3}p_{2}+\frac{1}{2}p_{3}+\frac{1}{3}p_{4}\,. (10) Second Family We now consider the second family of instances defined on the same graphs as the consistent instances from Section 2.1 but with a different arrival order. Let n be an even natural number. We have the following batches B_{1} , B_{2} and B_{3} • B_{1}:=\{e^{l}_{i},e^{r}_{i}\mid i\equiv 1\mod 2,\,\}\cup\{e_{1}\} • B_{2}:=\{e^{l}_{i},e^{r}_{i}\mid i\equiv 0\mod 2\} • B_{3}:=\{\hat{e}^{l}_{i},\hat{e}^{r}_{i}\mid i=1,\dots,n-2\} . So by Algorithm 2 we have M_{1}=B_{1} , M_{2}=B_{2} and M_{3}=B_{3} . The underlying graph again has a perfect matching, so the cardinality of a maximum matching is 2n-2 . Thus, we have the following constraint on the guarantee \gamma achieved by MinIndex, \frac{\mathbb{E}[|M|]}{2n}=\frac{n-1}{2(n-1)}p_{1}+\frac{n}{2(n-1)}p_{2}+\frac{2(n-2)}{2(n-1)}p_{3}\geq\gamma and therefore taking the limit as n\rightarrow\infty , we get the following constraint \frac{1}{2}p_{1}+\frac{1}{2}p_{2}+p_{3}\geq\gamma\,. (11) Finally, the trivial constraints based on consistent instances with n=1 and n=2 give the following constraints p_{1}\geq\gamma\ \ \ \ \ \text{and}\ \ \ \ \ \frac{1}{2}p_{1}+p_{2}\geq\gamma. (12) Linear Program So combining constraints ( 10 ), ( 11 ), and ( 12 ) along with probability constraints gives the following Linear Program bounding \gamma \displaystyle\mathmakebox[\widthof{$\underset{\displaystyle}{\mathrm{subject~to}}$}][l]{\underset{\displaystyle}{\mathrm{maximize}}}\quad\gamma \displaystyle\mathmakebox[\widthof{$\underset{\displaystyle\phantom{}}{\mathrm{subject~to}}$}][c]{{\mathrm{subject~to}}}\quad \displaystyle p_{1}\geq\gamma \displaystyle\frac{1}{2}p_{1}+p_{2}\geq\gamma \displaystyle\frac{1}{2}p_{1}+\frac{1}{2}p_{2}+p_{3}\geq\gamma \displaystyle\frac{1}{2}p_{1}+\frac{2}{3}p_{2}+\frac{1}{2}p_{3}+\frac{1}{3}p_{4}\geq\gamma \displaystyle p_{1}+p_{2}+p_{3}+p_{4}\leq 1 \displaystyle p_{1},\,p_{2},\,p_{3},\,p_{4}\geq 0\,. The above Linear Program achieves the optimal values 5/9 , where the optimal solution sets the parameters p_{1}=5/9 , p_{2}=3/9 , p_{3}=1/9 , and p_{4}=0 . Note that these parameters are exactly the parameters for which MinIndex from [ 3 ] achieves the guarantee 5/9 on all forests.