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
0
votes
1
answer
57
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$...
- 183
1
vote
1
answer
230
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 ...
- 183
0
votes
0
answers
112
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
272
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
566
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
1k
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
87
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
86
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
150
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
63
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
56
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,409
0
votes
0
answers
208
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
181
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
312
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 ...
- 882
3
votes
1
answer
727
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