eulerian-pathgraph theory
Consider the following graph G:
(a) Give a decomposition of G into cycles.
(b) Find an Eulerian circuit in G.
This is a very complicated graph and each time I am trying to find the solution I am getting lost in the middle. Is there any technique to solve such a problem?
Its really very difficult to find the Eulerian path.
Can anyone please help me?
Thanks in advance.
Yes it is possible.
Number the vertices $1,2, \dots 2n+1$.
Consider the sequence $1, 2n, 2, 2n-1, 3, 2n-2, \dots, n,n+1$, ignore $2n+1$ at the moment.
This gives a hamiltonian path in $K_{2n}$.
Now add $1$ to each vertex $\mod 2n$, to get $2,1,3,2n,4, 2n-1 \dots, n+1, n+2$. This can be visualized as writing the numbers $1,2, \dots, 2n$ in a circle and rotating the path. (see figure below).
Repeat this process of adding $1$, $n$ times. This gives you a set of $n$ edge-disjoint hamiltonian paths in $K_{2n}$. (We can show that by proving that (wlog) $1$ is first adjacent to $2n$, then $2,3$, then $4,5$ etc)
To each of these paths, add $2n+1$ at the end and join back to the first vertex of the path.
This gives you an Euler tour of $K_{2n+1}$ which starts and ends at vertex $2n+1$.
This can be computed in constant memory.
Note that this basically follows the (classic/folklore) construction that $K_{2n+1}$ can be decomposed into $n$ edge-disjoint Hamiltonian cycles. See this for instance, Modern Graph Theory, page 16.
In case that book is not accessible, here is a snapshot of the relevant part of that page:
Hint $$\deg_G(v)+\deg_{\bar{G}}(v)=6$$
You want both of them to be even, so you know exactly what the degrees should be. And you should be looking for $G$ so that both $G$ and $\bar{G}$ are connected.
Hint 2 If every vertex of $\bar{G}$ has degree $\geq \frac{7-1}{2}$ then $\bar{G}$ is automatically connected.
Best Answer
If a Eulerian circut exists, then you can start in any node and color any edge leaving it, then move to the node on the other side of the edge.
Upon arriving at a new node, color any other edge leaving the new node, and move along it.
Repeat the process until you