# Check if two graphs are edge-disjoint

Two undirected graphs $$G$$ and $$H$$ on the vertices $$1,2,\ldots,n$$ are disjoint if the intersection of their edge sets is empty. Assume both $$G$$ and $$H$$ are represented by adjacency matrices.

Describe an efficient algorithm that decides if $$G$$ and $$H$$ are disjoint. What is the complexity of your algorithm? Justify the correctness of your algorithm and your complexity claim.

What I am thinking is just picking an arbitrary vertex on either graph like $$G$$ and checking if we can reach a vertex from the other graph $$H$$ by running some simple traversal like DFS. Is there a better way? I am thinking what if we go through the adjacency matrix of one graph and check if any edge connects a vertex from one graph to the other.

• It seems to me that you have not really understood what it means that graphs are disjoints. Please re-read the definition. It is a good idea to use the adjacency matrix, but what does it mean that a edge connects a vertex from one graph to the other? Apr 22, 2021 at 23:17
• @Nathaniel isn't exactly what you said an edge connecting one vertex from one graph to the other? I am confused Apr 22, 2021 at 23:26
• Graphs may be edge disjoint and vertex disjoint, and your definition describes edge disjoint ones. So, they might have common vertices and your idea with DFS won't work. Apr 23, 2021 at 3:22
• so what is a better way? Apr 23, 2021 at 3:39
• As an example, you could have $E_G = \{\{1, 2\}, \{3, 4\}, \{5, 6\}\}$ and $E_H = \{\{2, 3\}, \{4, 5\}, \{6, 7\}\}$. This is an example of two disjoint graphs, because they have no edge in common. Is this clearer? Apr 23, 2021 at 6:39

The adjacency matrix $$A_G$$ of an undirected graph $$G=(V,E)$$ is defined as follows: $$A_G$$ is a $$V \times V$$ matrix, $$A_G(v,v) = 0$$ for all $$v \in V$$, and $$A_G(u,v) = 1$$ if $$\{u,v\} \in E$$ and $$A_G(u,v) = 0$$ if $$\{u,v\} \notin E$$.
Two graphs $$G,H$$ are edge-disjoint if there doesn't exist an edge $$\{u,v\}$$ which belongs to both of them. That is, $$G,H$$ are edges-disjoint if there do no exist $$u,v$$ such that $$A_G(u,v) = A_H(u,v) = 1$$.