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

278 questions
Filter by
Sorted by
Tagged with
29 views

### How to find a vertex-induced subgraph with Eulerian cycle [closed]

How to find a vertex-induced subgraph with an Eulerian cycle? The graph is connected and undirected. Is the problem NP-Hard?
1 vote
37 views

### Networks: Covering each edge and starting and ending at the same vertice when repeating edges must be involved.

I'm in year 11 and my question is regarding a certain topic that I've come across in my curriculum. The problem surrounding this question is about creating a path of minimum length that covers each ...
1 vote
175 views

### Prove that if a graph has an Eulerian path, then the number of odd degree vertices is either 0 or 2

I'm trying to prove that if a graph has an Eulerian path, then the number of odd degree vertices is either 0 or 2. My attempt. We know that the sum of the degrees of all vertices is twice the number ...
102 views

### When is the partition refinement graph Eulerian?

Let $n$ be a positive integer, and let $p(n)$ be the number of partitions of $n$. For two partitions $p_1, p_2$ of the same integer $n$, we say that $p_2$ is a refinement of $p_1$ if the parts of $p_1$...
95 views

### Why is a bipartite graph in which every vertex has degree exactly $2$ is simply a cycle?

I am trying to intuitively understand why a bipartite graph in which every vertex has degree exactly $2$ is simply a cycle. So far, I have tried to intuitively justify this by saying that an Eulerian ...
98 views

### Graph Theory - The Mouse problem [closed]

Edward the mouse has just finished his brand new house. The floor plan is shown below: Edward wants to give a tour of his new pad to a lady-mouse-friend. Is it possible for them to walk through ...
43 views

74 views

### Finding path lengths by the power of adjacency matrix of an undirected graph

The same question was asked almost 7 years ago. It turned out to be a matter of terminology in different textbooks between the terms "path" and "walk". While the answers addressed ...
943 views

### Is there a method for determining if a graph (undirected) is connected?

The textbook used in our class defines a connected (undirected) graph if for any two vertices $v,w\in G$ there is a path from $v$ to $w$. The examples used in the textbook show a visualization of a ...
51 views

### How it is possible that a graph has one edge such that every vertex has even positive degree?

I am trying to prove Let G be a connected graph with one edge such that every vertex has even positive degree. Prove that G has an Euler circuit. I know that a graph is an Euler circuit iff it is ...
82 views

### Euler cycle in a $m\times n$ rectangular grid.

Let $G=(V,E)$ a graph which consists in an $m\times n$ rectangular grid as the image shows: I need to find the values of $m,n$ for which this graph has an Euler cycle (or euler circuit, don't repeat ...
1 vote
89 views

### Existence of Euler $uv$-path $\iff$ all vertices except possibly u,v are even

A statement in my course says that : “A connected graph $G$ contains an Euler $uv$-path if and only if all vertices except possibly $u,v$ are even.” I agree with the $\implies$ direction, but in the ...
938 views

100 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.
42 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 ...
55 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 ...
143 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 ...
1 vote
149 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'...
304 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 ...
575 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 ... 