Mathematics

D. Zack Garza

12:00 AM

(A hint here is that you'll need every vertex to have even valence.)

Another hint is that you can have multiple edges between any two nodes.

manooooh

@D.ZackGarza you are right: we have more than two vertex of odd valence (the $v_1,v_2,v_3,v_4$)

D. Zack Garza

Whoops, yeah, correction to my hint: you need zero or exactly two odd valence vertices.

manooooh

It has Euler path!! We start from $v_4$: $v_4\to e_4\to v_2\to e_1\to v_1\to e_2\to v_2\to e_3\to v_2\to e_7\to v_3\to e_6\to v_2\to e_5\to v_4$

Well, that's probably an Euler cycle...

D. Zack Garza

Unfortunately, this re-introduces Hamiltonian paths as well -- just travel around the outer edge.

manooooh

Yeah... I'm almost done; it seems too difficult for me!

D. Zack Garza

12:06 AM

The key is thinking about what proved the previous graph didn't have a Hamiltonian path - at some point, you get "stuck" at a vertex.

manooooh

@D.ZackGarza yes, that "stuck vertex" is a vertex such that if we remove it, we disconnect the graph. I understand this, but I can't figure out how to meet the 2 conditions simultaneously

D. Zack Garza

Think about something like this: you can traverse every edge by starting at the bottom, going up, looping the sides, then going up again.

But can you visit every vertex without backtracking?

No matter what choice you take in the middle, you get stuck at a dead-end.

manooooh

This has Euler path: $v_5\to e_6\to v_1\to e_1\to v_2\to e_2\to v_1\to e_5\to v_4\to e_4\to v_1\to e_3\to v_3$: we passed through all edges just once

@D.ZackGarza this explains why this graph hasn't Hamiltonian path

D. Zack Garza

Right - there is at least 1 Euler path, so the graph is Eulerian. But the graph isn't Hamiltonian, which requires some proof.

But instead of checking all possible paths, you can reduce to checking two cases: what happens when a potential path passes through $v_1$?

Case 1, you go to $v_2$ or $v_4$. But now your path must end, otherwise you are forced to take the remaining edge back to revisit $v_1$.

But if your path ends at $v_2$, you must have visited $v_3$, for example. But once you enter $v_3$, you can't leave, so your path can only have started at (say) $v_3$.

But now your path can not visit $v_5$, a contradiction. But the same argument goes through if I'd chosen $v_5$ instead of $v_3$ in that last sentence.

And the same argument again goes through if I replace $v_2$ by $v_4$ in the sentence before that.

manooooh

@D.ZackGarza if we don't start at $v_1$, we need at some point to pass through $v_1$. When we have to visit another vertex we must pass through $v_1$, repeating $v_1$. The other case is if we start at $v_1$: then the same occurs, since if we go to any other vertex, to go back, we need to pass through $v_1$, repeating this vertex. Is this correct?

Hence, this graph does not have Hamiltonian graph since we must pass through $v_1$ more than once

D. Zack Garza

12:23 AM

For case 1, if you don't start at $v_1$, then yes I agree -- but you'd want to say why you're forced to revisit $v_1$. For a slick example, you can note that removing $v_1$ disconnects the graph completely.

You have to pass through $v_1$ as your first move, but then you have 3 more vertices to visit, and the only way to get there is through $v_1$.

manooooh

@D.ZackGarza yes, that's an excellent example!!

D. Zack Garza

For case 2, yep, very similar. If you start at $v_1$, whatever choice you make, you've only visited 1 vertex and you need 2 more. But every path to them goes through $v_1$.

manooooh

Can you help me about finding a graph that has Hamiltonian path but not Euler path?

tigre

Is an open subset of a quasi-compact space necessarily quasi-compact aswell (with the subspace topology)? I thought it was true originally, but then couldn't write down a proof yet (although I proved that closed subsets are quasi-compact along the way)

D. Zack Garza

@manooooh So the idea is to cook up a graph where you can visit each vertex once, but are forced to re-use an edge.

manooooh

12:31 AM

@D.ZackGarza exactly

tigre

Oh wait, an open subset of a hausdorff space is hausdorff, so I can just use euclidean space + Heine Borel to give a counterexample (meaning the failure of compactness of an open bounded subset of euclidean space is due to lack of quasi-compactness, and not hausdorffness)

D. Zack Garza

@manooooh That one's slightly trickier. Try something like two closed cycles, then connect them up with one single edge.

@tigre Probably false, because [0, 1] is compact (and thus quasicompact), but (0,1) is neither.

tigre

@D.ZackGarza Yeah that's what I realised in the above paragraph

manooooh

tigre

$(0,1)$ isn't quasi-compact, giving a counterexample. But are you sure you're right when you say it's not Hausdorff? Or you meant neither to compactness and quasicompactness, in which case I obviously agree

manooooh

12:41 AM

@D.ZackGarza ^^^^^^ I think I followed your steps but came up with no edge forcing

D. Zack Garza

@manooooh So it's worth checking - is there a Hamiltonian path? I think so, right, because you could just go from B to D. Now try to make a path that uses every edge.

manooooh

@D.ZackGarza it has Hamiltonian path: $B\to1\to A\to3\to C\to4\to D$

I am not sure if I understand you correctly

tigre

$B\stackrel{1}{\to}A\stackrel{3}{\to}C\stackrel{4}{\to}D$

D. Zack Garza

@tigre Right, just referring to the two versions of compactness.
(Hausdorff restricts to subsets just fine I think, you only have to worry about quotients.)

manooooh

@tigre it is the same as I wrote! But this graph has Euler path

tigre

12:47 AM

$A\stackrel{1}{\to}B\stackrel{2}{\to}A\stackrel{3}{\to}C\stackrel{4}{\to}D\stackrel{5}{\to}C$

I was just suggesting a better way to type set

D. Zack Garza

@manooooh So you'll want to modify this graph a little - you want to make it so there's no way to use every edge exactly once.

manooooh

Oh, thank you!

D. Zack Garza

So what about deleting edges $2, 4$ and making a new edge from $B\to D$?

It's almost immediate that this will just be a cycle, so that won't quite work.

So a further modification would be putting a new vertex $E$ in the middle, with 1 edge to everything else.

(The idea here is that you somehow want to force every choice of edges to "strand" you somewhere)

manooooh

This has Hamiltonian path: $A\stackrel{1}{\to}B\stackrel{2}{\to}D\stackrel{3}{\to}C\stackrel{7}{\to}E$

I am not able to prove that it does not have Euler path

Ultradark

1:07 AM

1

Q: Is there a name for this mapping? $(x,\phi(x)) \mapsto \big(\frac{1}{\phi(x)},\frac{1}{x}\big)$

Is there a name for this mapping? Does it appear in the literature, and where can I read about it more? How can I understand it best? $$ (x,\phi(x)) \mapsto \big(\frac{1}{\phi(x)},\frac{1}{x}\big) $$ If $f(x)=e^x$ and $g(x)=\frac{1}{\ln(x)}$ then let $\phi(x)=f(g(x)).$ I think it is some sort ...