Skip to main content

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.

Filter by
Sorted by
Tagged with
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 ...
Felix's user avatar
  • 11
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 ...
cheesepizza's user avatar
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 ...
Roh4n's user avatar
  • 11
1 vote
1 answer
55 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$. ...
Vibhaas Srivastava's user avatar
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. ...
lrussell's user avatar
-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 ...
Bark Jr. Jr.'s user avatar
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 ...
Amanda Wealth's user avatar
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 ...
Siddd's user avatar
  • 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 ...
Ulaş's user avatar
  • 73
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 ...
divadusthegreat's user avatar
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 ...
Florian Ragwitz's user avatar
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 ...
Mailbox's user avatar
  • 927
0 votes
0 answers
19 views

Graph theory : Travel to each Edge at least one and returning to the starting Node with the Shortest path in a Weighted Graph?

I would like to travel to each edge of the weighted graph at least once choosing the shortest path, i know this problem is similar to the Chinese Postman Problem CPP, but the difference here is that ...
Kakita The Third's user avatar
2 votes
2 answers
89 views

Which is correct Euler path or Euler trail?

Since path cannot have repeated vertices, the definition for A graph which exactly two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component ...
Alan von Turing's user avatar
0 votes
1 answer
45 views

Eulerian graph with $46$ vertices and $45$ edges [closed]

Is $G$ a graph which has an isolated vertex and its other connected component is $C_{45}$ an Eulerian graph? To be an Eulerian graph, could it happen that our graph is not connected?
J P's user avatar
  • 893
-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?
QC_Pod's user avatar
  • 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 ...
hello's user avatar
  • 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 ...
Mark's user avatar
  • 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$...
Hasan Zaeem's user avatar
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 ...
Princess Mia's user avatar
  • 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 ...
user2899944's user avatar
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,...
Princess Mia's user avatar
  • 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 ...
Princess Mia's user avatar
  • 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 ...
Princess Mia's user avatar
  • 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, ...
False Equivalence's user avatar
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 ...
Sarban Bhattacharya's user avatar
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)$ ...
Mimo's user avatar
  • 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 ...
OneMoreGamble's user avatar
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, ...
Edward H's user avatar
  • 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 ...
tetra4892's user avatar
-1 votes
1 answer
43 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, ...
Ayush Singh's user avatar
1 vote
1 answer
113 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 ...
Nathan Usevitch's user avatar
-1 votes
1 answer
629 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 ...
Theo's user avatar
  • 23
3 votes
2 answers
182 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 \...
yuanming luo's user avatar
0 votes
1 answer
104 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 ...
Moobie's user avatar
  • 103
3 votes
3 answers
2k 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 ...
neon tangerine's user avatar
0 votes
1 answer
59 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 ...
User124356's user avatar
  • 1,617
2 votes
1 answer
119 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 ...
Fabrizio G's user avatar
  • 2,117
1 vote
0 answers
113 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 ...
Kilkik's user avatar
  • 1,952
2 votes
3 answers
1k 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)...
Amere's user avatar
  • 21
0 votes
1 answer
36 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 ...
Smylic's user avatar
  • 7,016
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. ...
user avatar
0 votes
1 answer
774 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 ...
Pol's user avatar
  • 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 ...
karparvar's user avatar
  • 5,782
0 votes
0 answers
89 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 ...
karparvar's user avatar
  • 5,782
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$...
rainingagain's user avatar
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 ...
rainingagain's user avatar
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 ...
cleanplay's user avatar
  • 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$ ...
zhengyuansu's user avatar
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 ...
HarveyR's user avatar
  • 65

1
2 3 4 5 6