All Questions
Tagged with eulerian-path discrete-mathematics
65
questions
2
votes
1
answer
28
views
Constructing Paths in a Connected Graph with Odd-Degree Vertices
I am working on a problem and would appreciate some insights or suggestions on how to approach it.
Problem:
Let G = (V, E) be a connected graph where n is the number of vertices in V that are of odd ...
- 65
2
votes
2
answers
89
views
Which is correct Euler path or Euler trail?
Since path cannot have repeated vertices, the definition for
A graph which exactly two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component
...
2
votes
0
answers
107
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$...
- 97
0
votes
1
answer
195
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 ...
- 3,019
0
votes
2
answers
67
views
Confused about how to find de Bruijn sequence from Eulerian tour
I am not following how wikipedia constructs a de Bruijn sequence from an Eulerian tour here. When our Eulerian tour visits vertices $000,000, 001, 011, 111, 111, 110, 101, 011,
110, 100, 001, 010, 101,...
- 3,019
0
votes
0
answers
38
views
Are there at least $|V|$ Eulerian tours in $G$ if $G$ is even degree and connected? (My proof)
I believe there to be at least $|V|$ Eulerian tours in $G$ if $G$ is even degree and connected, and want to confirm that my reasoning of this is sound. (I am using the definition of Eulerian tour to ...
- 3,019
0
votes
0
answers
73
views
Prove by induction on the length of the walk that whenever it visits a vertex, it has traversed an odd number of edges incident to it
Say we walk on a finite, connected, even-degree graph with no self loops in the following way: we start from an arbitrary vertex $s \in V$, at each step choosing an untraversed edge incident to the ...
- 3,019
2
votes
2
answers
105
views
Combinatorics graphs for $2k+1$ representatives from $k $ different countries.
I'm having trouble with the following question :
Representatives from $1+2k$ countries come to an international conference, $k$ representatives from each country.
Is it possible to seat the $k(2k+1)$ ...
- 23
0
votes
0
answers
92
views
e <= 3v - 6 for planar graph question: why does every face (of a planar graph) have to have at least three sides?
Can't we make a face with just two edges(sides) and two vertices? We just connect those two vertices twice each with different edges and we can make a face between the two edges with only two vertices ...
3
votes
1
answer
215
views
Enumerating “Cyclic Double Permutations”
This is a generalization of a question first asked by loopy walt on Puzzling Stack Exchange: https://puzzling.stackexchange.com/q/120243. I asked the following version of the question in the comments, ...
- 142
0
votes
0
answers
61
views
Understanding which conditions a graph has a Eulerian Path
The graph $Q_n$ is a graph with 2n vertices, where each vertex is associated with a string of 1's
and 0's of length n, and where two vertices are adjacent if and only if their associated strings
...
- 53
3
votes
3
answers
2k
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 ...
- 197
2
votes
1
answer
119
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 ...
- 2,117
1
vote
1
answer
27
views
Does there exist Eulerian quadrangulations that are not 1- or 2-degenerate?
I am looking for Eulerian planar quadrangulations that are not 1- or 2-degenerate, but I cannot seem to find such graphs.
Note: a graph is Eulerian if and only if every vertex has an even degree. ...
user931598
0
votes
1
answer
774
views
Graph problem about roads built between towns [closed]
There are 10 cities in a country. The Government starts to build direct roads between the cities, but with random access, it can build direct road between two cities even if there is already another ...
- 21