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
0
answers
495
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,485
1
vote
0
answers
848
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 $...
- 870
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 ...
- 870
0
votes
2
answers
822
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 ...
- 870
1
vote
1
answer
643
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
0
votes
1
answer
79
views
Maximal graph not containing a subdivision of $K_5$ is $2$-connected?
I am trying to prove that a graph not containing no subdivisions of $K_5$, such that the addition of any edge would result in the existence of such a subdivision, is $2$-connected.
I already know the ...
- 485
0
votes
2
answers
65
views
How many Eulerian circuits from the node 0 are there in this graph? [duplicate]
I am new to this field, and I face with a question that asks me to count how many Eulerian circuits start from node 0 in this graph. The answer from the book is 264 but I feel that the answer is wrong....
0
votes
1
answer
250
views
Consecutive edges on Eulerian Circuit
Given an Eulerian graph G and 2 edges adjacent on the same vertex. Is there an Eulerian circuit that these two edges are consecutive? ie e1 - V1 - e2.
- 69
3
votes
4
answers
1k
views
Drawing the grid without lifting the pen
The below shape consist of $24$ segments with unit length. if we want to draw this shape without lifting the pen, what is the minimum length of the line we should draw?
$1)25\quad\quad\quad\quad\quad\...
- 1,159
0
votes
0
answers
513
views
If $G$ is a connected graph, then $G$ contains an Euler circuit if and only if every vertex has even degree (Misunderstanding of terminology).
I believe that I must be misunderstanding some of the terminology here. To my understanding, the included image is a connected graph where $\{ v_1,e_1,v_2,e_2,v_3,e_3,v_1 \}$ is contained within $G,$ ...
- 207
1
vote
1
answer
854
views
Find the shortest route to visit at least once all edges of a undirected weighted non-Eulerian graph
I'm trying to adress the following algorithmic problem using graph theory and Python:
I (personaly) want to find the shortest route I would follow to run through all streets of my district. I don't ...
- 21
5
votes
2
answers
1k
views
How can one justify if the graph is planar from adjacency matrix?
Given an adjacency matrix of a graph $G$, I was asked to do the following without drawing the graph:
A) Find the vertex of largest degree.
B) Does the graph have an Euler Circuit?
C) Is the graph ...
- 12.7k
0
votes
1
answer
98
views
Simple connected eulerian graph $G = (V, E)$ cannot be bipartite if $(V, E - \{e_1,e_2,e_3\})$ is also eulerian
Let $G = (V, E)$ be a simple connected eulerian graph, I was asked to prove that it cannot be bipartite if $(V, E - \{ e_1,e_2,e_3 \})$ is also eulerian.
While processing my proof I came up with this ...
- 123
1
vote
1
answer
83
views
Relationship between the parity of the number of forests in a graph and Eulerianness
Given a connected multigraph $G$, consider the number of forests in it – subsets of the edge set of $G$ that form no cycle, empty set included. This is a specific value $T_G(2,1)$ of the Tutte ...
- 104k
0
votes
2
answers
1k
views
Determine if edge is a bridge in a graph
I would like to implement Fleury’s algorithm to find Eulerian trails in a graph. This algorithm requires me to tell if a given edge is a cut edge (bridge).
Is there a more effective way of doing this ...
