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.
292
questions
-1
votes
1
answer
43
views
Eulerian trail (or Eulerian path) [closed]
I found this question in one oldie book
It is possible to draw figure A below without lifting your pencil in such a way that you never draw the same line twice. However, no matter how hard you try, ...
- 27
1
vote
1
answer
113
views
What rigid graphs can be decomposed into triangles such that each edge is in exactly one triangle?
Is there a general algorithm/condition to tell if a graph can be decomposed into triangles such that each edge is in exactly one triangle (the graph $G$ has a set of subgraphs such that each subgraph ...
-1
votes
1
answer
629
views
Show that if a connected graph has exactly two vertices of odd degree, then every Euler trail must start at one of these vertices and end at the other [closed]
Here is the question;
I am unsure of how to continue with this proof and don't know if what I have so far is right. What I have so far is this;
Let a connected graph $G$, have two vertices of odd ...
- 23
3
votes
2
answers
182
views
Is this degree sequence planar?
For the degree sequence [6,6,4,4,4,4,2,2,2,2]. Then this graph has $f = 10$ by euler's formula. Let $T$ be the number of triangles. Then the inequalities $2e = 36 \geq 3T + 4(10 - T)$ shows that $T \...
- 651
0
votes
1
answer
104
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 ...
- 103
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
0
votes
1
answer
59
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 ...
- 1,617
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
0
answers
113
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 ...
- 1,952
2
votes
3
answers
1k
views
Prove that graph isn't Eulerian
Let $G$ be a regular graph with even number of vertices and odd number of edges. Show that $G$ isnt an Eulerian graph.
I'm not sure if my solution is correct/misses something:
$|V(G)| = 2k%$ and $|E(G)...
- 21
0
votes
1
answer
36
views
What is the maximum and minimum length of Eulerian cycle possible in graph on $n$ vertices?
Consider all graphs on $n$ vertices. What the longest and the shortest Eulerian cycles do they have?
Such question arised recently on StackExchange, but it was deleted eventually, because OP wanted to ...
- 7,016
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
0
votes
0
answers
39
views
Why is this graph a connected Eulerian one?
In the well-known article of Oystein Ore titled "A problem regarding the tracing of graphs", Elemente der Mathematik, 6 (1951), 49-53, he proves that an Euler graph $G$ is arbitrarily ...
- 5,782
0
votes
0
answers
89
views
The only cut vertex in a graph
Let a graph $G$ be arbitrarily traversable from a vertex $v$, i.e., any trail in $G$ initiatng from $v$ ultimately results in an Eulerian $v-v$ circuit. Let $v$ be a cut-vertex in $G$. Is it true that ...
- 5,782