Connectivity graph-codes

The symmetric difference of two graphs G(1), G(2) on the same set of vertices V is the graph on V whose set of edges are all edges that belong to exactly one of the two graphs G(1), G(2). For a fixed graph H call a collection. of spanning sub-graphs of H a connectivity code for H if the symmetric difference of any two distinct subgraphs in. is a connected spanning subgraph of H. It is easy to see that the maximum possible cardinality of such a collection is at most 2(k'(H)) <= 2(delta(H)), where k'(H) is the edge-connectivity of H and delta(H) is its minimum degree. We show that equality holds for any d-regular (mild) expander, and observe that equality does not hold in several natural examples including any large cubic graph, the square of a long cycle and products of a small clique with a long cycle.