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.
278
questions
-2
votes
1
answer
29
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?
- 1
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
175
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,807
2
votes
0
answers
102
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$...
- 77
0
votes
1
answer
95
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 ...
- 2,143
-1
votes
1
answer
98
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 ...
- 275
0
votes
2
answers
43
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,...
- 2,143
0
votes
0
answers
37
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 ...
- 2,143
0
votes
0
answers
66
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 ...
- 2,143
1
vote
0
answers
48
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
44
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
87
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
49
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
201
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, ...
- 111
0
votes
0
answers
43
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
...
- 43
-1
votes
1
answer
38
views
Eulerian trail (or Eulerian path) [closed]
I found this question in one oldie book
It is possible to draw figure A below without lifting your pencil in such a way that you never draw the same line twice. However, no matter how hard you try, ...
- 27
0
votes
1
answer
85
views
What rigid graphs can be decomposed into triangles such that each edge is in exactly one triangle?
Is there a general algorithm/condition to tell if a graph can be decomposed into triangles such that each edge is in exactly one triangle (the graph $G$ has a set of subgraphs such that each subgraph ...
-1
votes
1
answer
363
views
Show that if a connected graph has exactly two vertices of odd degree, then every Euler trail must start at one of these vertices and end at the other [closed]
Here is the question;
I am unsure of how to continue with this proof and don't know if what I have so far is right. What I have so far is this;
Let a connected graph $G$, have two vertices of odd ...
- 23
3
votes
2
answers
142
views
Is this degree sequence planar?
For the degree sequence [6,6,4,4,4,4,2,2,2,2]. Then this graph has $f = 10$ by euler's formula. Let $T$ be the number of triangles. Then the inequalities $2e = 36 \geq 3T + 4(10 - T)$ shows that $T \...
- 651
0
votes
1
answer
74
views
Finding path lengths by the power of adjacency matrix of an undirected graph
The same question was asked almost 7 years ago. It turned out to be a matter of terminology in different textbooks between the terms "path" and "walk". While the answers addressed ...
- 103
3
votes
3
answers
943
views
Is there a method for determining if a graph (undirected) is connected?
The textbook used in our class defines a connected (undirected) graph if for any two vertices $v,w\in G$ there is a path from $v$ to $w$. The examples used in the textbook show a visualization of a ...
- 197
0
votes
1
answer
51
views
How it is possible that a graph has one edge such that every vertex has even positive degree?
I am trying to prove Let G be a connected graph with one edge such that every vertex has even positive degree. Prove that G has an Euler circuit.
I know that a graph is an Euler circuit iff it is ...
- 1,607
2
votes
1
answer
82
views
Euler cycle in a $m\times n$ rectangular grid.
Let $G=(V,E)$ a graph which consists in an $m\times n$ rectangular grid as the image shows:
I need to find the values of $m,n$ for which this graph has an Euler cycle (or euler circuit, don't repeat ...
- 1,934
1
vote
0
answers
89
views
Existence of Euler $uv$-path $\iff$ all vertices except possibly u,v are even
A statement in my course says that :
“A connected graph $G$ contains an Euler $uv$-path if and only if all vertices except possibly $u,v$ are even.”
I agree with the $\implies$ direction, but in the ...
- 1,787
2
votes
3
answers
938
views
Prove that graph isn't Eulerian
Let $G$ be a regular graph with even number of vertices and odd number of edges. Show that $G$ isnt an Eulerian graph.
I'm not sure if my solution is correct/misses something:
$|V(G)| = 2k%$ and $|E(G)...
- 21
0
votes
1
answer
31
views
What is the maximum and minimum length of Eulerian cycle possible in graph on $n$ vertices?
Consider all graphs on $n$ vertices. What the longest and the shortest Eulerian cycles do they have?
Such question arised recently on StackExchange, but it was deleted eventually, because OP wanted to ...
- 6,390
1
vote
1
answer
27
views
Does there exist Eulerian quadrangulations that are not 1- or 2-degenerate?
I am looking for Eulerian planar quadrangulations that are not 1- or 2-degenerate, but I cannot seem to find such graphs.
Note: a graph is Eulerian if and only if every vertex has an even degree. ...
user931598
0
votes
1
answer
721
views
Graph problem about roads built between towns [closed]
There are 10 cities in a country. The Government starts to build direct roads between the cities, but with random access, it can build direct road between two cities even if there is already another ...
- 21
0
votes
0
answers
39
views
Why is this graph a connected Eulerian one?
In the well-known article of Oystein Ore titled "A problem regarding the tracing of graphs", Elemente der Mathematik, 6 (1951), 49-53, he proves that an Euler graph $G$ is arbitrarily ...
- 5,710
0
votes
0
answers
59
views
The only cut vertex in a graph
Let a graph $G$ be arbitrarily traversable from a vertex $v$, i.e., any trail in $G$ initiatng from $v$ ultimately results in an Eulerian $v-v$ circuit. Let $v$ be a cut-vertex in $G$. Is it true that ...
- 5,710
0
votes
1
answer
43
views
Are the following two properties of Eulerian graphs true?
Can someone help to verify the following two properties, perhaps by indicating what properties of eulerian graphs is used in them?
Q1: Let $G$ be a connected graph containing a Eulerian circuit. If $G$...
- 165
1
vote
1
answer
180
views
"Give an example of a graph whose vertices are all of even degree, which does not contain a Eulerian Path"
I was given the above question in a test. I really struggle to see how it is possible that a Eulerian trail/path can fail to exist in a graph with all even degree vertices. When you consider that a ...
- 165
0
votes
0
answers
94
views
number of paths between opposite boundaries of a cube
There is a calculation of the number of surface paths (with no backtracking allowed) between opposite corners of a Rubik's cube. I am interested in paths on an $L\times L\times L$ cube, where $L$ is ...
- 409
1
vote
1
answer
222
views
Prove that an undirected connected graph $G$ contains an Euler circuit by some properties of its fundamental cut-set matrix and connectivity.
Let $G$ be an undirected connected graph. $\forall v∈V(G)$, $G-v$ (remove the node and all of its relevant edges from the graph) is still a connected graph. Besides, the fundamental cut-set matrix $S$ ...
- 13
0
votes
1
answer
487
views
Is a cycle for a graph containing all edges of the graph necessarily an Euler cycle?
Under the definition that an Euler cycle is a cycle passing every edge in G only once, and finishing on the same vertex it begins on.
I have reasoned that the answer to this would be no, since it ...
- 65
1
vote
1
answer
733
views
Prove this algorithm for finding the Eulerian path/cycle in a undirected graph
Take a look at the procedure (source: https://cp-algorithms.com/graph/euler_path.html)
procedure FindEulerPath(V):
iterate through all the edges outgoing from vertex V;
remove this edge from the ...
- 63
1
vote
2
answers
85
views
Property of a connected graph with $\text{deg(all nodes)}=\text{even}$
In my lecture nodes it is proposed that for a connected graph $G$ with the degree of all nodes being even, there exist two paths between any two nodes $x,y\in G$ with no common edges. From the very ...
- 175
0
votes
1
answer
77
views
Do We Have Any Special Transform For $(i)(e^{(-2iw)})$
I have Signals and Systems course. Generally we use $j$ instead of $i$. So in here you can think $j$ as a complex number $i$.
In the solution which uses Euler's first step, i see that transform.
$2j(e)...
- 11
2
votes
1
answer
100
views
Every bipartite Eulerian graph is a Hamilton graph
This is a true/false question I'm trying to solve to prepare for my exam. Could someone confirm my answer and help me prove it?
What I think: false, but I can not come up with an example.
- 115
0
votes
1
answer
42
views
Are all 4-regular Hamiltonian graphs Euler graphs?
This is a true/false question I'm trying to solve to prepare for my exam.
Could someone confirm my answer?
What I think:
true, because the graph then has only even degrees and the graph is also ...
- 115
0
votes
0
answers
55
views
Is it possible to arrange handshakes in this way?
I am reading Eulerian graphs from this pdf. In page 210, exercise 9.5.7, I am stuck at following problem.
Each of 8 persons in a room has to hand shake with every other person as per the following ...
- 5,211
0
votes
0
answers
143
views
Number of simple paths in a graph
I intend a simple path to be a path in a graph in which an element does not appear twice.
Now, let $ G = \langle V,E\rangle $ be a graph.
My professor told us that the maximum number of simple paths ...
- 101
1
vote
1
answer
149
views
Does a Maximal Planar graph have Euler cycle
I was given today in the text the following information:
G is a maximal planar graph over $n>2$ vertices.
given that $\chi(G)=3$, prove there is an Euler Cycle in the graph.
Now, I believe this isn'...
- 111
2
votes
3
answers
304
views
Does the graph contain a Hamiltonian and an Euler cycle?
Question:
Let $G=(V_n,E_n)$ such that:
G's vertices are words over $\sigma=\{a,b,c,d\}$ with length of $n$, such that there aren't two adjacent equal chars.
An edge is defined to be between two ...
- 872
3
votes
1
answer
575
views
Prove/Disprove that you can't draw an X inside a box without lifting the pen
I apologize if this is a repost, but I couldn't find the question in case it does actually exist here.
I tried and it seems to me that we cannot draw a square with its diagonals without lifting the ...
user525755
0
votes
0
answers
411
views
Domino eulerian path problem
I'm looking at an example of an eulerian path problem, and it's not clear to me what the problem is.
There are N dominoes, as it is known, on both ends of the Domino one number is written(usually ...
- 1,417
1
vote
0
answers
725
views
$G$ has $2k>0$ vertices of odd degree if and only if there exists a partition of the edges of $G$ into $k$ open Eulerian trails.
Let $G$ be a connected graph, show that $G$ has $2k>0$ vertices of odd degree if and only if there exists a partition of the edges of $G$ into $k$ open Eulerian walks.
Attempt:
$\Rightarrow )$ Let $...
- 850
0
votes
2
answers
1k
views
Prove that $G$ is Eulerian if and only if every block of $G$ is Eulerian.
Prove that $G$ is Eulerian if and only if every block of $G$ is Eulerian.
Attempt:
If G is Eulerian, then G has a partition into cycles edge-disjoint. I don't know how to apply it, though.
If every ...
- 850
0
votes
2
answers
679
views
Give an example of a graph $G$ such that $G$ and $G'$ are not Eulerian, but $G$ has an Eulerian trail and $G'$ does not have an Eulerian trail.
Give an example of a graph $G$ such that $G$ and $G'$ are not Eulerian, but $G$ has an Eulerian trail and $G'$ does not have an Eulerian trail.
I was thinking that $T_n$ is not Eulerian but it does ...
- 850
1
vote
1
answer
494
views
Prove that complement of graph is Eulerian
I have to prove that complement of Eulerian graph with odd number of vertices and with maximum degree of vertex $\le \frac{n}{2}$ where $n$ is number of vertices, is also Eulerian. I proved that every ...
- 533