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
1
vote
1
answer
34
views
Worst Case Solution for directed Chinese Postman Problem
The Problem
Let $G$ be a directed graph with $n$ vertices. How long is a shortest circuit that visits every edge in the worst case? That is how long is the solution to the directed Chinese Postman ...
- 368
0
votes
1
answer
1k
views
Eulerian Graph with odd number of vertices
I am struggling with the following question:
Prove that for each odd integer $n ≥ 3$, there exists exactly one
Eulerian graph of order $n$ containing exactly three vertices of the
same degree and at ...
CommunityBot
- 1
2
votes
1
answer
28
views
Constructing Paths in a Connected Graph with Odd-Degree Vertices
I am working on a problem and would appreciate some insights or suggestions on how to approach it.
Problem:
Let G = (V, E) be a connected graph where n is the number of vertices in V that are of odd ...
- 65
1
vote
1
answer
54
views
Finding an Eulerian path on complete graphs
I want to prove the following algorithm to find an Eulerian path in a complete graph:
In the complete graph $K_{n}$ where $n = 2k + 1, k \in \mathbb{Z}^+$, let us label the vertices $1, 2, ..., n$. ...
- 7,016
0
votes
0
answers
33
views
Spanning Trees with 1/2 the edges in a Eulerian Graph
I was attempting the following problem:
Let $G$ be a connected simple graph. (a) If $G$ is eulerian with an even number of vertices, then it has a spanning subgraph $G'$ such that every node $i$ has ...
- 47.4k
6
votes
1
answer
206
views
Properties of prime sum graphs
The prime sum graph $P_n$ on the vertex set $V = \{1,\dots, n\}$ has an edge $e = xy$ when $x+y$ is prime. It is easy to show that any such $P_n$ is bipartite (put odd numbers in one part and evens in ...
- 1,919
3
votes
1
answer
174
views
Lemma for proving the Euler's theorem
I was studying graph theory when a question came to my mind.
I am referring to a particular way to prove Euler's theorem, viz. the fact that every multigraph (i.e. undirected graph without loops but ...
- 571
-1
votes
1
answer
43
views
What are necessary and sufficient conditions to have a negative cycle in a directed graph with some negative edges? [closed]
Trying to test Johnson’s algorithm with over 100 vertices but it doesn’t work if there is a negative cycle. So I’m trying to write code to construct graphs with some negative weights (about 10% of the ...
- 1,488
0
votes
1
answer
40
views
counting Eulerian circuits on complete directed graph
I have a complete directed graph $G$ (including self-loops). How can I count the number of Eulerian circuits on $G$?
For example, in the simple case of $n=2$, there are clearly 4 Eulerian circuits. ...
- 10.5k
0
votes
0
answers
22
views
Proving a graph has an Eulerian path if the components of the graph are both Eulerian.
Suppose that a graph $G$ has a bridge $xy$ such that the components of $G-xy$ are both Eulerian. Prove that G has an Eulerian path. What can you say about the beginning and end of the trail?
I ...
- 1
0
votes
1
answer
57
views
Eulerian Trail proof in Walk Through Combinatorics
I'm struggling with the proof of Eulerian trail in walk through combinatorics.
As you now, the theorem states that "A connected graph G has a closed Eulerian trail if and only if all vertices of ...
- 47.4k
6
votes
1
answer
152
views
Is it possible to go over all lines of a grid with a pencil without lifting it or going over a drawn line?
Is it possible to go over all lines of an infinite grid with a pencil without lifting it or going over a drawn line ?
The pencil can cross through a segment already drawn but cannot go over an already ...
- 47.4k
8
votes
3
answers
22k
views
Prove that Petersen's graph is non-planar using Euler's formula
Prove that Petersen's graph is non-planar using Euler's formula.
I know that $n - m + f = 2$. But should I count $f$ and prove that the summation does not equal to two or solve to get $f =7$ and ...
- 927
3
votes
1
answer
190
views
How many ways of traversing every arc of a complete digraph exactly once from a given starting vertex are there?
Given a set of $n$ states $V = \{ s_1, s_2, \ldots, s_n \}$, and a complete digraph $G = (V, A)$ where $A = \{ (a,b) \mid (a,b) \in V^2\; \text{and}\; a \neq b \}$, I'm interested in finding cyclic ...
- 17.7k
0
votes
1
answer
54
views
"If a vertex appears $k$ times in an eulerian circuit, then it must have degree $2k$" - Why?
I need help understanding this part of this proof from Graphs and Digraphs (7th ed):
Theorem 3.1. A connected multigraph is eulerian if and only if every vertex has
even degree.
The authors of this ...
- 44.3k