# 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
Filter by
Sorted by
Tagged with
1 vote
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 ...
• 11
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 ...
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 ...
• 11
1 vote
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$. ...
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. ...
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 ...
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 ...
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 ...
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 ...
• 73
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 ...
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 ...
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 ...
• 927
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 ...
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 ...
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?
• 893
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?
• 13
1 vote
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
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 ...
• 7,880
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$...
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 ...
• 3,019
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 ...
• 313
67 views

• 651
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 ...
• 103
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 ...
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 ...
• 1,617
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 ...
• 2,117
1 vote
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 ...
• 1,952