Adjacency inference in H (i.e., gray dashed edges in graph B) from matched vertices u, v in graph A.

<p>Vertices a, b are matched vertices that have not been contracted. Vertices c, d are unmatched. Black solid edges are derived from PG(G_obs), CPG(G_obs) or contracted edges. The four different paths found by <b>find_path(u, v)</b> are as follows: (1) (u, v) (green), (2) (u, a, b, v) (blue), (3) (u, b, a, c, v) (orange), and (4) (u, d, v) (pink). In graph A, the first two paths are odd and form two even cycles – (u, v, u) and (u, a, b, v, u) – by adding the gray edge (u, v) in the top right panel. The former disappears after contraction, while the latter generates a new black edge (a, b) in the bottom left panel. The last two paths are merged by two same gray edges (u, v) to form an even cycle – (u, b, a, c, v, u, d, v, u) – that is contracted and generates two new black edges, (b, d) and (c, d). Two numbers on each edge of graph A indicate the copy IDs of the two corresponding vertices in graph B.