Questions tagged [eulerian-path]
This tag is for questions relating to Eulerian paths in graphs. An "Eulerian path" or "Eulerian trail" in a graph is a walk that uses each edge of the graph exactly once. An Eulerian path is "closed" if it starts and ends at the same vertex.
292
questions
-2
votes
1
answer
38
views
How to find a vertex-induced subgraph with Eulerian cycle [closed]
How to find a vertex-induced subgraph with an Eulerian cycle?
The graph is connected and undirected.
Is the problem NP-Hard?
- 13
1
vote
0
answers
37
views
Networks: Covering each edge and starting and ending at the same vertice when repeating edges must be involved.
I'm in year 11 and my question is regarding a certain topic that I've come across in my curriculum. The problem surrounding this question is about creating a path of minimum length that covers each ...
- 11
1
vote
1
answer
617
views
Prove that if a graph has an Eulerian path, then the number of odd degree vertices is either 0 or 2
I'm trying to prove that if a graph has an Eulerian path, then the number of odd degree vertices is either 0 or 2.
My attempt.
We know that the sum of the degrees of all vertices is twice the number ...
- 7,880
2
votes
0
answers
107
views
When is the partition refinement graph Eulerian?
Let $n$ be a positive integer, and let $p(n)$ be the number of partitions of $n$. For two partitions $p_1, p_2$ of the same integer $n$, we say that $p_2$ is a refinement of $p_1$ if the parts of $p_1$...
- 97
0
votes
1
answer
195
views
Why is a bipartite graph in which every vertex has degree exactly $2$ is simply a cycle?
I am trying to intuitively understand why a bipartite graph in which every vertex has degree exactly $2$ is simply a cycle. So far, I have tried to intuitively justify this by saying that an Eulerian ...
- 3,019
-1
votes
1
answer
230
views
Graph Theory - The Mouse problem [closed]
Edward the mouse has just finished his brand new house. The floor plan is shown below:
Edward wants to give a tour of his new pad to a lady-mouse-friend. Is it possible for them to walk through ...
- 313
0
votes
2
answers
67
views
Confused about how to find de Bruijn sequence from Eulerian tour
I am not following how wikipedia constructs a de Bruijn sequence from an Eulerian tour here. When our Eulerian tour visits vertices $000,000, 001, 011, 111, 111, 110, 101, 011,
110, 100, 001, 010, 101,...
- 3,019
0
votes
0
answers
38
views
Are there at least $|V|$ Eulerian tours in $G$ if $G$ is even degree and connected? (My proof)
I believe there to be at least $|V|$ Eulerian tours in $G$ if $G$ is even degree and connected, and want to confirm that my reasoning of this is sound. (I am using the definition of Eulerian tour to ...
- 3,019
0
votes
0
answers
73
views
Prove by induction on the length of the walk that whenever it visits a vertex, it has traversed an odd number of edges incident to it
Say we walk on a finite, connected, even-degree graph with no self loops in the following way: we start from an arbitrary vertex $s \in V$, at each step choosing an untraversed edge incident to the ...
- 3,019
1
vote
0
answers
55
views
Eulerian Graphs and Cycle Decompositions
I have been trying to find the following references, it would be helpful if I am linked to either of the two, both of them would be ideal.
[1] H. Fleischner, Cycle decompositions, 2-coverings, ...
0
votes
1
answer
49
views
Is the following a Path?
While watching a lecture on Eulerian path, I found the following slide
Now my question is how is the above walk a path? The vertex w is getting repeated twice and then $ue_1ve_2we_3xe_4ye_5w$ should ...
2
votes
2
answers
105
views
Combinatorics graphs for $2k+1$ representatives from $k $ different countries.
I'm having trouble with the following question :
Representatives from $1+2k$ countries come to an international conference, $k$ representatives from each country.
Is it possible to seat the $k(2k+1)$ ...
- 23
0
votes
0
answers
92
views
e <= 3v - 6 for planar graph question: why does every face (of a planar graph) have to have at least three sides?
Can't we make a face with just two edges(sides) and two vertices? We just connect those two vertices twice each with different edges and we can make a face between the two edges with only two vertices ...
3
votes
1
answer
215
views
Enumerating “Cyclic Double Permutations”
This is a generalization of a question first asked by loopy walt on Puzzling Stack Exchange: https://puzzling.stackexchange.com/q/120243. I asked the following version of the question in the comments, ...
- 142
0
votes
0
answers
61
views
Understanding which conditions a graph has a Eulerian Path
The graph $Q_n$ is a graph with 2n vertices, where each vertex is associated with a string of 1's
and 0's of length n, and where two vertices are adjacent if and only if their associated strings
...
- 53