# Questions tagged [eulerian-path]

An Eulerian path is a trail in a graph which visits every edge exactly once.

174 questions
1answer
35 views

### Upper bounds on the solution to a directed route inspection problem

If for any strongly connected digraph $D$ we define $\lambda(D)$ to be the length of any shortest closed walk traversing every arc in $D$, then does there exist some constant $m\in\mathbb{R}$ such ...
1answer
51 views

### Does every Euler circuit pass through all vertices?

I have a question. In my homework I was assigned the following question: Given a connected graph in which the degree of all vertices is 2, prove that this graph is a cycle. (Prove that there is a ...
1answer
27 views

### Give a counter example to show that if $G$ and $H$ are both Eulerian but only one is connected, then the cartesian product is not Eulerian

Well it's easy to prove that if the graphs $G$ and $H$ are both connected and Eulerian then $G\square H$ is Eulerian since for both G and H every vertex has even degree. But this statement is not true ...
1answer
31 views

### Are Euler trails and tours of a graph the same as Hamilton paths and cycles of the corresponding “edge graph”?

Is knowing information about Euler paths and Euler tours about a graph $G$ the same as knowing information about Hamilton paths and cycles of the graph $H$ obtained from $G$ such that vertices of $H$ ...
2answers
54 views

### Find the number of degree 1 vertices in terms of n and d

Fix an integer $d>1$. Let $G$ be a tree with $n$ vertices, and every vertex can have either degree $1$ or $d$. Find the number of degree $1$ vertices in terms of $d$ and $n$. I've been working on ...
1answer
21 views

### Graph which is Bipartite, has an Euler circuit, but not a Hamiltonian circuit

Is there a graph which is bipartite, has an Euler circuit, but not a Hamiltonian circuit? I know the answer is yes, but if you consider something like this: I don't think this would be bipartite, ...
1answer
22 views

### Find Euler trail given a function that finds Euler Circuit.

Assume you have a computer program called print-EulerCircuit(G) that returns a euler circuit given a graph as an input. A Euler trail is a walk that hits every ...
0answers
58 views

### Only one graph of order 5 has the property that the addition of any edge produces an Eulerian graph. What is it?

This is a homework question. However, I don't think that such a graph exists. Here's my attempt at proving that (I know I'm wrong; please tell me where I went wrong!): For contradiction, assume such ...
0answers
11 views

### Path / Graph problem with X nodes looking for Y paths with the most similar length.

I have the following graph / path problem: There is exactly 1 start node and 1 end node. There are also X (in this case 7) nodes, each connected to all other nodes and the start and end node with ...
1answer
64 views

### Eulerian Circuits. Prove that if every edge of a graph G lies on an odd number of cycles, G is Eulerian.

The question I need to answer is: Prove that if every edge of a graph G lies on an odd number of cycles, then G is Eulerian. I'm having trouble wrapping my head around this question. I've found an ...
1answer
19 views

### Graph Problem: find X path lengths which are closest to each other (similar to shortest path)

I have the following problem: 1 Start point 1 End point 7 Knots / waypoints which you have to visit in any order All 9 knots are connected with each other. All paths have to start at the start point ...
1answer
58 views

### Finding Euler path using powers of adjacency

Context: I'm studying an introductory course to Discrete Applied Mathematics, and am new to the context of graphs. Knowing that a graph can be represented as an adjacency matrix, say we have the ...
0answers
41 views

### n-dimensional Euler path

Is it possible to have a one dimensional euler path/trail and how does it work and look like? All the examples i find on wikipedia shows only 2 dimensional examples. I cannot find a one dimensional or ...
2answers
53 views

### A Graph G where each vertex has an even degree can be split into cycles by which no cycle has a common edge.

According to this, a polygon of (4 vertices and 4 edges e.g: a square, a rectange ...) each vertex has a even degree of 2. should be able split that into 2 cycles, but it cannot be done. why ? Here ...
2answers
28 views

### Equivalent characterization of Eulerian circuits

Background A connected graph has an Eulerian circuit if every vertex has even degree. I am thinking about a certain classification of connected graphs where, for a connected graph $G$, every cut ...
1answer
39 views

### Graph theory problem and connected components

In a connected graph $G$ where degree of every vertex $v$ is even, show that $G\setminus v$ has at most $\dfrac{1}{2}\deg(v)$ connected components. $G\setminus v$ is the graph which is left after ...
1answer
27 views

### Euler's formula and graph duality

I am confused with this video on YouTube. In the graph attached, the edge taken by the Randolph (the blue pi creature) forms a spanning tree and the remaining edge (colored in red) is taken by ...
1answer
30 views

### Hamilton path and Euler circuits in Cycle graph

Can $C_n$ has $2*n$ Euler circuits and $3*n$ Hamilton paths in the Cyclic graphs?
1answer
236 views

### When does the complete bipartite graph K n,m have an Euler Trail(Path)?

So I know that an Euler trail must have no more than two odd degree vertices. So does this mean that either $n$ or $m$ must be odd? Or is it $n = m + 1$?
1answer
40 views

### Need prove a Graphs with n >= 5 with a Euler path and without Hamilton Path and Hamilton Cycle exist.

I already proved a Euler Tour can't exist because all degrees would have to equal a number divisible by 2 but a Euler Path requires two odd degrees. I still have to prove a graph exists that contains ...
1answer
123 views

### Route Inspection Problem

The route inspection problem, is to find a shortest closed path that visits every edge of a connected undirected graph. If $G = (V,E)$ is a tree, then any route inspection tour has $2\vert E\vert$ ...
0answers
54 views

### Minimum number of Euler paths

Now we know that if number of odd degree vertices in a graph is $0$ or $2$ it an Euler path and if its higher it doesn't. I want to know if its indeed higher, in how many Euler paths can you cover the ...
1answer
91 views

### Algorithm that check if given undirected graph can have Eulerian Cycle by adding edges

Assume that G is a connectable undirected graph, what is the best algorithm in terms of complexity, that check if graph G can have an Eulerian cycle by adding edges? I thought of their two cases G ...
1answer
82 views

### Difference between chromatic number and minimal vertex covering

I have just started learning graph theory not long ago, this is a past year problem and I got the correct answer by chance(True/False questions), wanted to check my understanding on this site. My ...
0answers
40 views

### On the hamiltonicity of the line graph and the graph?

Definition: Let $G$ be a graph, the line graph of $G$ denoted of $L(G)$ is defined as follows: 1-The vertices of $L(G)$ are the edges of $G$ 2-Two vertices of $L(G)$ are adjacent iff their ...
1answer
63 views

### Lagrange vs Eulerian coordinates

I have to solve this exercise about the Eulerian and Langrangian approach and I would like if you can take a look on my answers: In the evening, at $t=0$ say, the temperature increases southwards in ...
2answers
55 views

### Graph with conditions

G is a graph whose vertex set is $\{1,2, ... , 82\}$, vertices $i$ and $j$ are adjacent iff $|i-j| \mod 4 = 0 \text{ and } i \neq j$. (a) Calculate the chromatic number of $G$. (b) Is $G$ Eulerian? ...
2answers
72 views

### Is there a simple planar graph with n vertices which has the most possible edges that is also Eulerian

For each $n$, where $n>=3$, are there any graphs in the set of all graphs with $n$ vertices that are simple and planar, and have the most possible number of edges, that also have an Eulerian path ...
1answer
164 views

### Can we consider an Euler Circuit as a Euler Path?

If we have a Graph with Euler Circuit can we the consider it as a special Euler Path that start and end in the same Node? I am asking because the Condition of Euler Path is that we have 0 or 2 Nodes ...
1answer
132 views

### Eulerian graph with odd-degree vertices?

I'm reading about this theorem. But then I see this graph, which seems to be a counter-example, with the Eulerian trail being $e_1e_2...e_{11}$, and the odd-degree vertices being $v_1$ and $v_3$. ...
2answers
114 views

### Is there a $6$ vertex planar graph which which has Eulerian path of length $9$?

Let $G$ be a simple graph with Eulerian path of length $9$. There're two non-adjacent vertices $u, v$ in $G$ and if we connect $u$ and $v$ by an edge $G$ is not planar anymore. Does such a graph exist ...
0answers
114 views

### What is connection between Euler graphs, bipartite graphs and having even number of vertices?

Prove or disprove: If $G$ is an Euler graph with even number of vertices then it's bipartite. If $G$ is an Euler and bipartite graph then the number of its vertices is even. The second ...
0answers
27 views

### Eulerian directed graphs $2$-norm is 1

I stumbled upon a strange question about eulerian graphs. Let $G$ be a directed Eulerian graph. Prove that it's normalized adjacency matrix $A$ has $\| A\|_2=1$. It looked strange to me and I ...
1answer
43 views

### Is the graph formed by GP series of adjacency matrix, Eulerian?

Suppose I have a Graph G(V,E) and A is the adjacency matrix of G. The graph thus formed by creating a GP series of adjacency matrix $P=A+A^2+A^3+....+A^{n-1}$ Is this graph Eulerian? A is such ...
1answer
20 views

### Euler Circuits and Paths on 3D Surfaces

I am new to graph theory and am confused as to whether I am researching in the right area. I am working on a project which requires creating closed contours on the surface of a cylinder, and this is ...
1answer
58 views

### Is this a counter example to the Eulerian Trail definition?

Wikipedia says: An undirected graph has an Eulerian trail if and only if exactly zero or two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected ...
2answers
175 views

### Non isomorphic graphs with closed eulerian chains

I need to construct 2 graphs that are non isomorphic and have 3 of the following properties. Same number of vertices Same number of edges Both contain a closed eulerian path I was thinking of the ...
3answers
271 views

### Sufficient condition for graph isomorphism assuming same degree sequence

We assume graph to be simple undirected. In general, having the same degree sequence is not sufficient for two graphs to be isomorphic. A trivial example is a hexagon which is connected and two ...
1answer
114 views

### Question on degree sequence of eulerian, hamiltonian bipartite graph

I've gathered that it requires a cycle with degree 10 to be considered hamiltonian and it is bipartite so there can not be any odd cycle, lastly it is eulerian hence every edge set can be partitioned ...
1answer
375 views

### How to find Eulerian path in the given graph?

I have plotted the following graph (was given by the adjacency matrix): And I have to find the Eulerian path there and emphase this. I am concerned because my book says that the further action ...
1answer
165 views

### Graph Theory - Hamiltonian Cycle, Eulerian Trail and Eulerian circuit

Is it possible to draw a graph that has an Eulerian trail as well as a Hamiltonian Cycle but does not have an Eulerian circuit?
2answers
39 views

0answers
90 views

### Alternating path from any vertex to any vertex [duplicate]

Statement: Given a connected graph with all edges coloured in one of two colours (red and black), so that for each vertex the number of incident red edges is equal to the number of black edges. Proof:...
1answer
43 views

### The ratio between Central Eulerian Numbers and the sum of Eulerian Numbers at a fixed level converges to zero

The Central Eulerian Numbers are given by the formula $$C(n) = \sum_{j=0}^n(-1)^j(n-j)^{2n-1}\binom{2n}{j}$$ This represent the Eulerian Number $E(2n-1, n)$ where E(n, k) = \sum_{j=0}^k(-1)^j(k-j+...