Two questions about eulerian and hamiltonian graphs.

Question

I have 2 questions in graph theory.

$\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $Graph\ 1$

$\ \ \ $

$\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $Graph\ 2$

$\ \ \ $

$\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $Graph\ 3$

1) Let $Graph$ = $(G, E)$, $G$ is set of vertices, $E$ is set of edges.

Let $S(Graph) := \{X\subset E|(G,E\setminus X)$ is eulerian.

I want to find $min_{X \in S(Graph\ 1)} |X|$.

2) I want to find hamiltonian cycles in $Graph\ 2$ and $Graph\ 3$(or prove that graph is not hamiltonian).

$\ $

Tnak you for any help!

Answer 1

Graph 2 isn't Hamiltonian. You can check that the graph is symmetric on interchanging the two high-degree vertices, or the vertices of any joined pair of degree-3 vertices, or any pair of the degree-4 vertices. Label the vertices of the graph 1,2,3 on the top row; 4,5, then 6,7, then 8,9.

Since the graph is symmetric on swapping vertices 2 and 9, the only way 2-9 could fail to be in the cycle is if 7-9-8 and 7-2-8 were both in the cycle. That's a problem if we want our cycle to contain nine vertices, so 2-9 is in the cycle; similarly 3-5.

Since the graph is symmetric on swapping 7 and 8, wlog 9-7 is in the cycle. Then 2-8 is in the cycle. But now we have to make the cycle hit vertex 5: either 8-5 is an edge, so 3-7 must be (and contradiction), or 7-5 is an edge (and so 3-8 is, contradiction).

---

Graph 3 isn't Hamiltonian. Label the vertices $1,2$ on the top row, then $3,4,5,6$ on the middle, then $7,8$ bottom row. Then any Hamiltonian cycle must contain 1-4-7, because vertex 4 has degree 2. What happens to vertex 3? Well, we go both in and out of vertex 3, so at least one of the edges 3-1, 3-7 is in the cycle; the whole graph is symmetric about the middle axis, so wlog 3-1 is in the cycle. That rules out 3-7 (which would close a triangle), so 3-6 is in the cycle.

Now, 1-2 can't be in the cycle because we can only use 1 once. Then 7-2 can't be in the cycle (because then the only way to leave 2 would be through 2-6, which would close the loop). That means we have to somehow enter and leave vertex 2 through just one edge.

Answer 2

Graph 3: Not Hamiltonian. Look at that vertex of degree 2. There is only one way in/out. Now consider that vertex directly to the left of it. Once you go in/out from that degree 2 vertex, how do you get in/out of this other one (which has degree 3)?

Answer 3

Graph 1 has six vertices of odd degree, so to make it Eulerian by deleting a set $X$ of edges, you have to delete at least three edges, to reduce those six odd degrees to even numbers. By good fortune, the six odd-degree vertices can be paired up so that each pair is joined by an edge; delete those three edges, and you win.

In general graphs, you might not be so lucky. There might not be such a nice pairing of the odd-degree vertices. Then you'd have to delete paths (rather than single edges) joining the odd-degree vertices, and the problem would come down to choosing those paths so as to minimize their total length.