2 added 8 characters in body

If G and H are graphs with n vertices, Δ(G,H) can be Θ(n2).

Here is an example which shows this. Let n=4k+1 be a prime. Define two graphs G=(V,E) and H=(V,FH=(V,E′) by V={0,1,2,…,4k}, E = {{i,j} | 1 ≤ ((j−i) mod n) ≤ k}, F E = {{i,j} | k+1 ≤ ((j−i) mod n) ≤ 2k}. Note that G and H are both unions of k edge-disjoint Hamiltonian circuits, which implies that αi,j(G)=αi,j(H)=2k for any distinct i and j. Let S={0,1,2,…,2k−1}. Then Δ(G,H) ≥ CH(S)−CG(S) = k(3k+1)−k(k+1) = 2k2 = Θ(n2).

There is no reason to believe that this is the maximum of Δ(G,H) for given n, but it is obviously optimal up to a constant factor.

1

If G and H are graphs with n vertices, Δ(G,H) can be Θ(n2).

Here is an example which shows this. Let n=4k+1 be a prime. Define two graphs G=(V,E) and H=(V,F) by V={0,1,2,…,4k}, E = {{i,j} | 1 ≤ ((j−i) mod n) ≤ k}, F = {{i,j} | k+1 ≤ ((j−i) mod n) ≤ 2k}. Note that G and H are both unions of k edge-disjoint Hamiltonian circuits, which implies that αi,j(G)=αi,j(H)=2k for any distinct i and j. Let S={0,1,2,…,2k−1}. Then Δ(G,H) ≥ CH(S)−CG(S) = k(3k+1)−k(k+1) = 2k2 = Θ(n2).

There is no reason to believe that this is the maximum of Δ(G,H) for given n, but obviously optimal up to a constant factor.