/sci/ - Science & Math

Can you define "decomposed into cycles"? Is it like, E can be partitioned into sets that can each be ordered to form cycles?

>>5657442
It means that the cycles are components of G

If i remember correctly, the general proof idea is that you start on a cycle and go round it until you reach a vertex that lies inside another cycle. then you go off into that cycle, and go round, etc, until you've gone round every edge.

this probably won't help

>>5657454
But Eulerian means you cant go over the same vertex twice, so what if you go into a cycle and then can't get out?

>>5657442
A graph G is said to be decomposed into a set of graphs H^1,...,H^k if each H^i is a
subgraph of G, and E(H1);...;E (H^k) is a partition of E(G)

>>5657457
Thats a Hamiltonian graph, Eulerian is only concerned with edges

>>5657454
>>5657457

very sketchy proof:

Remove the edges of a cycle C from G to get G'.

Then each component (cycle) of G' had a vertex in the C by connectedness. Now build an Eulerian trail by going round C until you hit a vertex in one of the components, and then go round that cycle (only on the first visit to that component). This will take you around every edge and back to the starting vertex.

>>5657480
>Then each component (cycle) of G' had a vertex in the C by connectedness.

No. Say that G is:
1<->2<->3<->4

G is connected and decomposable into the cycles 1<->2, 2<->3 and 3<->4. If you remove C=1<->2, you get G'=2<->3<->4, and the cycle 3<->4 from G' has no vertex in C.

I agree that it must be something like that, trying to translate connectivity on cycles instead of just vertices and removing edges from the cycles that we used, but it's not that direct.

>>5657504
sorry by this notation a<->b do you mean that there is are two edges between a and b, or just one? if two then that is not a simple graph (sorry, assumed we're talking about simple graphs) and if one, that is not a cycle.

or am i confusing your notation?

>>5657504
also, removing 1<->2 leaves the *singular* component 2-3-4-2 which it does have a vertex in

>>5657505
Yeah, by 1<->2 I meant that there is a connection from 1 to 2 and a connection from 2 to 1. I think that's the context in which Eulerian graphs are usually defined (directed graphs in which it is possible to have symmetrical connections).

>>5657508
Oh, so basically you mean you should consider "maximum" cycles C, somehow (cycles that are not included into larger cycles)? Then yeah, you're probably right.

>>5657513
ah okay, well, I think my point still holds that the singular component of 2->3->4->3->2 has a vertex in 1->2->1, and my method still works, i.e the path would be

1->2->3->4->3->-2->1

>>5657515
yep, probably something to do with maximal cycles in there.

to be honest this is all very hazy and sketchy for me. I had a quick look at some of my old graph theory notes and adapted this "proof" from a proof that a graph with all even vertices of even degree is eulerian, so if you can prove that you might be on the way

>>5657521
Yeah, graph theory is also a few years back for me, I can't think about it properly without writing down a lot of stuff anymore.

Anyway, I've been trying on my own and I think that basically I end up with the same idea as yours. I'd present it by induction on the number of those maximum cycles:

If you can partition E into a single cycle, then you're done.

Assume that any graph such that can be decomposed into exactly n maximum cycles is Euclidean. Consider a graph G whose set of edges E can be decomposed into n+1 maximum cycles.

Consider a subgraph G' of G composed of n of its n+1 maximum cycles. That subgraph, restricted to the vertices that it visits, is Euclidean by induction hypothesis, let's call <span class="math">C_e[/spoiler] one of that graph's Euclidean cycles. By connectivity, it must have at least one vertex v in common with the leftover cycle C. Because <span class="math">C_e[/spoiler] and C are cycles, you can make them at vertex v, so that <span class="math">C_e=v\to v_1\to v_2\to v_3\to \dots\to v_k\to v[/spoiler] and <span class="math">C=v\to v_1'\to v_2'\to v_3'\to \dots\to v_l'\to v[/spoiler], where the edges of C and <span class="math">C_e[/spoiler] are disjoint. Therefore G admits the Euclidean cycles <span class="math">v\to v_1\to v_2\to v_3\to \dots\to v_k\to v\to v_1'\to v_2'\to v_3'\to \dots\to v_l'\to v[/spoiler].

Sounds good to you?

Isn't this second part of the theorem false?
If you take K_5, a connected (and complete) graph with 5 vertices, it can be decomposed into cycles and yet it is not Eulerian.

>>5657745
It is indeed Eulerian. I'm assuming that you are referring to the one called "pentatope graph" in http://mathworld.wolfram.com/EulerianGraph.html

The pentagon is a cycle, and the star is a cycle too, just start from any vertex, draw the pentagon and you'll end up where you started, then draw the star, you'll end up where you started again, and all vertices will be on that cycle.

>>5657573
Also I just realized I wrote Euclidean for Eulerian everywhere in this post. Damn...

>>5657757
Oh right I was thinking for some reason you had to use each edge at least once, duh, thanks

>>5657763
You do. You have to use each edge exactly one, but you can go several times through the same vertex.

>>5657766
Haha, sorry, meant vertex. Thanks for the help man