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
0 votes
0 answers
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 ...
user avatar
  • 5,571
0 votes
1 answer
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$...
user avatar
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 1
0 votes
0 answers
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 ...
user avatar
  • 389
1 vote
1 answer
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$ ...
user avatar
0 votes
1 answer
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 ...
user avatar
  • 61
1 vote
1 answer
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 ...
user avatar
1 vote
2 answers
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 ...
user avatar
  • 157
0 votes
1 answer
40 views

Do We Have Any Special Transform For $(i)(e^{(-2iw)})$

I have Signals and Systems course. Generally we use $j$ instead of $i$. So in here you can think $j$ as a complex number $i$. In the solution which uses Euler's first step, i see that transform. $2j(e)...
user avatar
0 votes
0 answers
27 views

Formal inductive proof of find tour algorithm.

The find tour algorithm takes a graph G and vertex s and starts walking from vertex $s \in{V}$, at each step choosing any untraversed edge incident to the current vertex, until it gets stuck. I know ...
user avatar
2 votes
1 answer
41 views

Every bipartite Eulerian graph is a Hamilton graph

This is a true/false question I'm trying to solve to prepare for my exam. Could someone confirm my answer and help me prove it? What I think: false, but I can not come up with an example.
user avatar
  • 85
0 votes
1 answer
28 views

Are all 4-regular Hamiltonian graphs Euler graphs?

This is a true/false question I'm trying to solve to prepare for my exam. Could someone confirm my answer? What I think: true, because the graph then has only even degrees and the graph is also ...
user avatar
  • 85
0 votes
0 answers
50 views

Is it possible to arrange handshakes in this way?

I am reading Eulerian graphs from this pdf. In page 210, exercise 9.5.7, I am stuck at following problem. Each of 8 persons in a room has to hand shake with every other person as per the following ...
user avatar
0 votes
0 answers
42 views

Number of simple paths in a graph

I intend a simple path to be a path in a graph in which an element does not appear twice. Now, let $ G = \langle V,E\rangle $ be a graph. My professor told us that the maximum number of simple paths ...
user avatar
0 votes
0 answers
86 views

De Bruijn sequence and graphs

Claim: In every De-Bruijn sequence all characters have the same number of occurrences. True/False? We went over De-Bruijn sequence in our algorithms class and I don't understand it at all. Running a ...
user avatar
0 votes
0 answers
67 views

Hamiltonian Cycle and Euler Cycle

True/False: Let $G$ be a connected undirected graph such that all vertices have even degrees. Every Euler cycle in $G$ is also a Hamiltonian cycle if and only if $G$ is a cycle graph. I think this one ...
user avatar
  • 1
0 votes
0 answers
77 views

Proving that every vertex in a graph with an Euler circuit has an even degree: is this proof correct?

Below is my proof. Is it correct, and how can I improve it? Prove that: If G is a graph in which there exists an Euler circuit, then every vertex has an even degree. Let’s imagine a dot is taking a ...
user avatar
1 vote
1 answer
77 views

Does a Maximal Planar graph have Euler cycle

I was given today in the text the following information: G is a maximal planar graph over $n>2$ vertices. given that $\chi(G)=3$, prove there is an Euler Cycle in the graph. Now, I believe this isn'...
user avatar
  • 81
2 votes
3 answers
256 views

Does the graph contain a Hamiltonian and an Euler cycle?

Question: Let $G=(V_n,E_n)$ such that: G's vertices are words over $\sigma=\{a,b,c,d\}$ with length of $n$, such that there aren't two adjacent equal chars. An edge is defined to be between two ...
user avatar
  • 862
3 votes
1 answer
159 views

Prove/Disprove that you can't draw an X inside a box without lifting the pen

I apologize if this is a repost, but I couldn't find the question in case it does actually exist here. I tried and it seems to me that we cannot draw a square with its diagonals without lifting the ...
user avatar
  • 870
0 votes
0 answers
148 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 ...
user avatar
  • 1,280
1 vote
0 answers
256 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 $...
user avatar
0 votes
0 answers
41 views

Graph Theory drawing request

I'm practising drawing graphs. One of the questions I'm using : I discovered more than two vertices that have an uneven degree (degree shown as red number next to each vertex), for both odd and even $...
user avatar
  • 171
0 votes
1 answer
517 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 ...
user avatar
0 votes
2 answers
138 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 ...
user avatar
1 vote
1 answer
182 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 ...
user avatar
  • 503
0 votes
0 answers
38 views

A problem on Euler digraph and Combinatorics

I have met a problem in my course of combinatorics. First we define $W_{n,m}$ as the digraph with $$V=(\{0\} × [n]) ∪ (\{1\}×[m])$$ and $$E=\{(ξ,i)→(1−ξ,j)|ξ∈\{0,1\}, i∈[n], j∈[m], ξ=i+j\mod 2\}$$ we ...
user avatar
0 votes
1 answer
57 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 ...
user avatar
0 votes
2 answers
42 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....
user avatar
0 votes
1 answer
62 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.
user avatar
  • 69
3 votes
4 answers
447 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\...
user avatar
  • 967
1 vote
0 answers
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,$ ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 11
3 votes
2 answers
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 ...
user avatar
  • 11.9k
0 votes
1 answer
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 ...
user avatar
  • 123
1 vote
1 answer
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 ...
user avatar
  • 89.6k
0 votes
2 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
1 vote
2 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 2,947
0 votes
1 answer
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 ...
user avatar
3 votes
3 answers
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 ...
user avatar
  • 2,547
0 votes
0 answers
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, ...
user avatar
0 votes
0 answers
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 ...
user avatar
0 votes
1 answer
25 views

Show that this graph is a tree

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 ...
user avatar
  • 11.5k
0 votes
0 answers
30 views

Show that this directed graph is eulerian and hamiltonian

Define the directed graph $D_{n,k} = (V_{n,k},A_{n,k})$ for $k \ge 2$. The vertices are the $k$-dimensional vectors with values between 1 and $n$, that is $V=\{1,..n \}^k$. Two vertices $u=(u_1,...,...
user avatar
  • 405
0 votes
1 answer
204 views

A connected graph G has 12 vertices and 64 edges. Is G Hamiltonian? Is G Eulerian? [closed]

A connected graph G has 12 vertices and 64 edges. Is G Hamiltonian? Is G Eulerian? Do we have enough information to be able to tell? Not sure where to start with this one! Can anyone help me out?
user avatar
  • 3
0 votes
0 answers
34 views

Can a Graph be Proven to be Directional?

Here's a line from my textbook that I'm having trouble understanding: Let $G$ be a simple graph with $n$ vertices and $m$ edges. If $G$ is undirected then then $m\leq \frac{n(n-1)}{2}$, and if $G$ is ...
user avatar
  • 57

1
2 3 4 5 6