Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [eulerian-path]

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

1
vote
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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$ ...
2
votes
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 ...
0
votes
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, ...
0
votes
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 ...
2
votes
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 ...
2
votes
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 ...
0
votes
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 ...
1
vote
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 ...
4
votes
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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?
1
vote
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$?
1
vote
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 ...
3
votes
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$ ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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 ...
2
votes
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? ...
3
votes
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 ...
2
votes
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 ...
1
vote
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$. ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
2
votes
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 ...
2
votes
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 ...
1
vote
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?
1
vote
2answers
39 views

Proving the graph $V=\{S\subset\{1,2\ldots9\}\mid3\leq\left|S\right|\leq4\},\,\,\,E=\{(u,v)\mid u\subset v\}$ is connected

Let $G=\left\langle V,E\right\rangle$ be an undirected graph with $V=\left\{ S\subset\left\{ 1,2,\ldots,9\right\} \mid\left|S\right|\in\left\{ 3,4\right\} \right\}$ and $E\left\{ \left(u,v\right)\mid ...
1
vote
1answer
101 views

Determine if G is bipartite. Find a maximal path and Eulerian circuit in G.

Would I be correct to assume that a maximal path would be e-c-a-b-h-d-f-g? Is this my eulerian circuit: c-e-b-a-c-h-b-d-f-g-d-h-f-c? Also, am I right to say it is not bipartite because it contains an ...
1
vote
1answer
324 views

Graph Theory: Euler Trail and Euler Graph

- Background Information: I am studying graph theory in discrete mathematics. As I was reading my notes, I came across few definitions. I think I have noticed a pattern, but I need to confirm it with ...
2
votes
1answer
2k views

Proof for a graph has Euler tour iff each vertex has even degree

This is the proof: I was able to understand this proof except the last part. They consider the edge $\{u, v_i\}$ to prove that if $W$ is not the Euler tour then it is not the longest walk as well, as ...
1
vote
1answer
109 views

Find an Euler path

I don't have an answer for this exercise, so I'm asking you. Exercise: Draw a graph with 6 vertices with the degrees: 2, 3, 3, 4, 4, 4. Name the vertices a, b, c, d, e, f (in the order you want), and ...
1
vote
2answers
280 views

Proof - a vertex in a path has an even number of edges [duplicate]

Given a simple undirected graph, let's say we have a path of i edges that can repeat nodes but not edges i.e. nodes may come up more than once in the path but not the edges. NOTE : I never said ...
1
vote
1answer
33 views

eulerian circuit combinatorics [closed]

Let $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$ be two such graphs on the same vertex set $V$ that both have Eulerian circuit. Let $G_3 = (V, E_3)$ be the graph also on vertex set $V$ given by $E_3 = (E_1\...
0
votes
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:...
1
vote
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+...