# 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.

257 questions
Filter by
Sorted by
Tagged with
29 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 ...
26 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$...
1 vote
34 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 ...
27 views

### Number of eulerian subgraphs of $K_n$

I need an advice on how to approach this problem. It's a part of a project in Graph theory. How to determine a number of eulerian subgraphs of $K_n$ (complete graph with $n$ vertices)? It's part of a ...
29 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 ...
1 vote
44 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$ ...
262 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 ...
1 vote
98 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 ...
1 vote
80 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 ...
40 views

41 views

1 vote
80 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,$ ...
1 vote
162 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 ...
513 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 ...
51 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 ...
1 vote
53 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 ...
666 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 ...
1 vote
117 views

### Characterizing graphs for which the subdivision graph S(G) is Eulerian or Hamiltonian

I know that $G$ is Eulerian iff all of the vertex degrees are even. So my thinking is that for any cycle graph $C_n$, its subdivision graph is Eulerian because each vertex has degree 2 and adding a ...
1 vote
66 views

### Binary subsequence of size three, graph with euler cycle

Alan Tucker's Applied Combinatorics state, "A set of eight binary digits (0 or 1) are equally spaced about the edge of a disk. We want to choose the digits so that they form a circular sequence ...
1 vote
120 views

### Euler circuits for the graph

How many different Euler circuits are there in the graph that begins at $A$ and then visits $D$ as the immediate next vertex? My answer is $16$, and I suppose I have counted all possible such Euler ...
1 vote
29 views

### Basic question about Euler trails

In my lectures, we proved the following theorem: A graph $G$ has an Euler trail iff all but at most two vertices have odd degree, and there is only one non-trivial component. Moreover, if there are ...
40 views

### Does a eulerian cycle exist in this context?

I have a picture of a rectangle and a vertex off to the side. I'd like to know if, since a Euler cycle includes all edges of a graph exactly once, if a Euler cycle exists in this graph. Couldn't the ...
303 views

### 3-regular graph and two-way Euler circuit

A town-planner has built an isolated city whose road network consists of $2N$ roundabouts, each connecting exactly three roads. A series of tunnels and bridges ensure that all roads in the town meet ...
267 views

### Which complete graphs have an Euler tour? Which of the complete graphs have an Euler trail?

I think the complete graphs with odd vertices would be Euler tours, because they are connected and each vertex has even valency. I'm having trouble thinking through Euler trails and complete graphs, ...
43 views

### Determine whether there is Euler circuit

The exercise: Asks for both of Eulerian circuit and path circuit. Conditions: 1)-Should stop at the same point that started from. 2)- Don't repeat edges. 3)-Should cross all edges After long ...
Suppose we have a directed multigraph (a graph with loops and parallel edges), with vertex set $V=\{v_1,v_2,\cdots,v_n\}$, such that $d^+(v_i)=d^-(v_i)$ for every $i=1,2,\cdots,n$, i.e. indegree of ...