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
0answers
23 views

Examine if is Euler circle

enter image description here As you can see the vertices are $u_o,u_1,u_2,u_3,u_4,u_5$.As a result are 6 that means are even number. With the theory "a graph will contain an Euler circuit if all ...
0
votes
1answer
79 views

How do I write a proof that $G^C$ (G complement) has a Euler cycle in a general way?

So I'm basically failing my discrete mathematics class, with Graph Theory, because I don't know how to define something generally and not specifically, and all our teacher does is read the textbook ...
0
votes
0answers
23 views

Under which condition will a Euler graph's complement also be a Euler graph?

I'm thinking the condition is that the original graph G must have half of edges than its complete graph, but I'm not sure if that's correct. I appreciate any help, sorry for my English.
0
votes
0answers
61 views

How to show that a line graph of a graph L(G) has a Euler cycle if the original graph G has a Euler cycle?

The line graph $L(G)$ of a graph $G$ has a vertex for each edge of $G$, and two of these vertices are adjacent if and only if the corresponding edges in $G$ have a common end vertex. (a) Show that $L(...
0
votes
1answer
30 views

Connected graph with two vertices of odd degrees, not containing an Euler path?

The rules for an Euler path is: A graph will contain an Euler path if it contains at most two vertices of odd degree. My graph is undirected and connected, and fulfill the condition above. Yet those ...
0
votes
2answers
81 views

Bipartite Connected Graph, Eulerian Circuit

Give an example of a bipartite connected graph which has an even number of vertices and an Eulerian circuit, but does not have a perfect matching.
0
votes
1answer
31 views

Euler Cycle in directed cycle

I am trying to solve a problem which boils down to find whether all non-zero degree nodes in a directed graph form a simple cycle.This can be solved by checking whether there is euler cycle in ...
2
votes
0answers
23 views

Digraphs with exactly one Eulerian Tour

I’ve been thinking about the following problem from Richard Stanley’s list of bijective proof problems (2009). There, this problem is said to lack a combinatorial solution. The problem is the ...
1
vote
1answer
41 views

A vertex $v$ is extendible if and only if $G − v$ is a forest.

I need help understanding the solution to this problem. This problem has been answered here, however, my doubt is not addressed. Problem: Let $G$ be a connected Eulerian graph with at least $3$ ...
0
votes
1answer
39 views

Prove that de-bruijn graph has eulerian cycle?

Let $G_{2,n}$ be a de-bruijn graph. We remove the vertex 11...11 and the vertex 00...00 and all edges connected to them. Q: ...
0
votes
1answer
37 views

How to prove that there exists a specific path?

Let G(V,E) be an undirected graph. if there exists a vertex called u that its degree is not even then it is connected to another vertex ...
2
votes
0answers
44 views

Does every graph have a “double Eulerian walk”?

The graph is undirected. A walk is a sequence of vertices such that each pair in the sequence corresponds to an edge of the graph. Unlike paths, walks can repeat vertices. An Eulerian trail is a ...
0
votes
0answers
20 views

Is Euler Loop and Euler Circuit equivalent?

See Protocol Conformance Testing Using Unique Input/output Sequences: Page 22: Definition II.B.1: G is a graph with no isolated vertex. If there is a tour travelling through each edge once and only ...
0
votes
0answers
29 views

Variant of Euler´s Theorem for Digraphs

So I stumbled upon a problem. So I have to prove that for a Digraph $D$ without isolated vertices has oriented closed Eulerian circuit iff the Graph undirected graph $G$ of $D$ is connected and for ...
0
votes
1answer
30 views

How many Hamiltonian cycles are there in a graph with n vertices?

How many eulerian cycles are there in a graph with n vertices? The way that I see it there would be $\frac{n!}{(n!)(n-n)!}$ but that simplifies to 1 cycle and I know that there are more cycles than ...
1
vote
0answers
38 views

New to graph theory and I have some questions on basic definitions

So in my algorithms class we started learning the basics of graph theory and (as usual) I had to use the Internet as a supplement to my notes and found it to have more definitions but now I am unsure ...
0
votes
1answer
52 views

Any graph with an Euler circuit is connected.

So I started with defining an Euler circuit as a closed walk containing at least one edge, not repeating any edge, and ending the walk on the same vertex as it was started. Is this a full proof, ...
5
votes
0answers
30 views

Properties of prime sum graphs

The prime sum graph $P_n$ on the vertex set $V(P_n) = \{1,\dots, n\}$ has an edge $e = xy$ when $x+y$ is prime. It is easy to show that any such $P_n$ is bipartite (put odd numbers in one part and ...
0
votes
1answer
28 views

Eulerian Circuit-Cycle Decompositions

For some background information, Eulerian here refers to starting and ending on the same vertex (i.e. being closed). Also, the corollary below uses Theorem 3.4 which states a graph is Eulerian iff ...
1
vote
1answer
96 views

How can I solve the Rotating Drum problem for 64 segments? (Or at all)

For clarification, I am very bad at maths and the logic usually goes right over my head, however I am studying a reasonably high level of maths because I am a software and game development student. I ...
-1
votes
1answer
56 views

Chromatic Number of Eulerian Graph

I'm trying to find the chromatic number of an Eulerian graph of $81$ vertices where each vertex has degree $12$. I'm trying to use Brook's theorem, but I'm confused as to whether an Eulerian graph ...
0
votes
1answer
27 views

Let G be a connected graph where all vertices have even degree. Show that for each vertex v in G, c (G \ v) ≤ δ (v) / 2. c is the number of components

c is the number of connected components. Me and a friend were trying to prove this problem, but the observations we made, we sent them to our teacher and said that they not really true. We thought ...
0
votes
0answers
34 views

Hamiltonian Puzzle Algorithm

I know how to create a Hamiltonian path or circuit for a given grid size (in which all nodes are free). However I just wonder how to create specific type of puzzles like the ones given below. I'm ...
2
votes
2answers
34 views

Finding the inverse of line graphs L(G)

I just learned about line graphs $L(G)$ such that all vertices $v$ in $L(G)$ represent edges in $G$. Is there a way to inverse this process and for any graph $G$ find $G'$ such that $G$ represents ...
2
votes
1answer
55 views

Creating a $4 \times 4$ square grid using $5$ pieces of $8$-inch wires

We would like to create a $4$-by-$4$ square grid using pieces of wire such that the sides of the squares are $1$ inch and we are not allowed to cut the wires. Is it possible to create the grid by ...
0
votes
2answers
38 views

Checking the minimum length of a cycle in a graph with odd vertices.

I have the following graph: Obviously, this graph does not have an eulerian cycle because it has vertices with odd degree. However, how can I find the cycle that visits every edge with the minimum ...
-1
votes
0answers
38 views

Odd Vertices in Euler Path

Could somebody please explain why an Euler path cannot have $2n$ odd vertices if $n$ is an integer larger than or equal to $2$? I understand that the handshake lemma rules out odd numbers of odd ...
0
votes
1answer
50 views

Task about graph theory and Euler path. [closed]

Happy new year to all! Could you explain me with this task from my Discrete Mathematics examination? Suppose 𝐺 is a simple undirected graph with 𝑛 vertices, each having degree 5. a) For which ...
1
vote
1answer
26 views

Method to Traverse an Eulerian Circuit

Say we have a graph $G$ that has an Eulerian circuit. Break apart its edges into a disjoint union of cycles. Say it can represented as follows: $\{ C_1, C_2, ..., C_n\}$. Question: Is there a ...
0
votes
1answer
50 views

Eulerian graph confusing

Can an Eulerian graph be of edge connectivity 1? And can an Eulerian graph have vertex connectivity 1? Please show step how you done it.
1
vote
2answers
65 views

How can be found Euler path from a directed graph using hierholzer's algo?

The above graph contains an Euler Path & indegree and outdegree are equal in every node except the starting node 6 (Indeg[6] + 1 == Outdeg[6]) and finishing node 4 (Indeg[4] == Outdeg[4] + 1). ...
0
votes
0answers
36 views

How can I find a cyclic path in a graph

Is there any algorithm or approach to find a cyclic path within a graph, optimizing some cost function, e. g. maximizing a reward associated with edges. The optimal cyclic path would then be the one ...
0
votes
1answer
100 views

Proof of weakly connected finite directed graph is strongly connected if each of it's vertex has equal in degree and out degree

Hi I'm seeking for a formal proof of the question listed in the title. I'm a new learner that do not have extensive knowledge for that, So if any of you could be so kind to tell me and explain to me ...
8
votes
2answers
529 views

An ant walks on a cube over the diagonals of little cubes. Can it visit all little faces exactly once?

I have got this task at high-school math-contest seminar. The theme is graphs. Let us have $n \in \mathbb{N}$ and the cube $ n \times n \times n$. An ant can go over a diagonal of little cubes, but ...
0
votes
1answer
421 views

Is a Unicursal Graph an Euler Graph?

Euler graph is defined as: If some closed walk in a graph contains all the edges of the graph then the walk is called an Euler line and the graph is called an Euler graph Whereas a Unicursal ...
2
votes
1answer
50 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
257 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
88 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
91 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
596 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
58 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
32 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
195 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
17 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 ...
1
vote
1answer
778 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
25 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
381 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
2answers
351 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
120 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
46 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 ...

1
2 3 4 5