If we have two Eulerian graphs $H = (V,E)$ and $H' = (V, E')$ that are on the same set of $n \geq 5$ vertices and do not share any edges. Is the disjunction of $G$ and $H$ also Eulerian.
Asked
Active
Viewed 296 times
2 Answers
1
There's one quibble with the conclusion here.
Suppose that $H$ is a graph on vertex set $\{1,2,3,4,5,6\}$ with edges $\{12,13,23\}$ and $H'$ is a graph on the same vertex set with edges $\{45, 46, 56\}$. Then, even though $H$ and $H'$ are not connected, they are Eulerian: all components except one are isolated vertices, and so there is still a closed walk that visits every edge exactly once. However, the union of $H$ and $H'$ is not Eulerian, because you have two $3$-cycles, and can't get from one to the other.
On the other hand, if your definition of an Eulerian graph requires it to be connected, then you are fine.
Misha Lavrov
- 142,276
0
That proof looks correct to me, and you can even weaken the hypothesis. Instead of both of them having the same exact set of vertices, you can just assume $H$ and $H'$ share at least a single vertex, so that their sum is connected.
