If two graphs are subgraphs of each other, are they isomorphic? I was curious to know whether, when two graphs are subgraphs of each other, they are isomorphic. Is there a proof for this? I was using the idea from set theory that if two sets are subsets of each other, then they are equal.
Thanks
 A: Consider two graphs $G=(V,E)$ and $G'=(V',E')$ and suppose they are subgraphs of each other. Since $G$ is a subgraph of $G'$, we have that $V\subseteq V'$ and $E\subseteq E'$. Since $G'$ is a subgraph of $G$, we have that $V'\subseteq V$ and $E'\subseteq E$. Therefore, $V=V'$, $E=E'$, and $G=G'$.
EDIT: If by "subgraph" you actually meant that $G$ is isomorphic to a subgraph of $G'$ and vice versa, then the answer is different. There is the following counterexample. Let $G=(V,E)$ where $V=\mathbb{Z}$ and $E=\{(x,y): x\in\mathbb{Z}, y\in\mathbb{Z}\}$. Now let $G'=(V',E')$ where $V'=\mathbb{Z}\setminus \{0\}$ and $E'=\{(x,y):x\in\mathbb{Z},y\in\mathbb{Z},xy>0\}$ As you can see, $G$ is the complete graph of integers and $G'$ is the union of two complete graphs: one of positive integers and one of negative integers. Now $G\ncong G'$ because $G$ is connected and $G'$ is not. Now, to prove that each is isomorphic to a subgraph of the other:
$G'$ is obviously a subgraph of $G$ because $V'\subseteq V$ and $E'\subseteq E$. $G$ is isomorphic to a subgraph of $G'$ via the isomorphism $$f(x)=\begin{cases}2x & x>0\\ -2x+1 & x\le 0\end{cases}$$
Basically, $G$ is isomorphic to the subgraph of $G'$ containing only the positive integers.
A: Another counterexample: let 


*

*$G$ have underlying set $(0, 1)$ and edge relation $x<y$

*$H$ have underlying set $[0, 1]$ and edge relation $x<y$.
Clearly $G$ is a subgraph of $H$; but $H$ is also isomorphic to a subgraph of $G$ (think about the map $x\mapsto {x+1\over 3}$). And these graphs are not isomorphic - for example, $H$ has a vertex which sees every other vertex, while $G$ does not.

We can similarly get an undirected example: let $G$ have underlying set $(0, 1)\times (0, 1)$, $H$ have underlying set $[0, 1]\times [0, 1]$, and in each case let the edge relation be $(a, b)E(c, d)$ iff the line connecting $(a, b)$ and $(c, d)$ has nonnegative slope (treating vertical as nonnnegative, say) - and not connecting any point to itself. 
