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
vote
1
answer
497
views
drawable graph theory
What are all the tricks that make a graph drawable? I know that a graph is drawable when you can draw the graph without lifting your pen off the paper and without retracing any edges. I know that if ...
- 221
2
votes
1
answer
1k
views
When is a linegraph Eulerian?
So I know that for a simple Eulerian graph, its linegraph is also Eulerian. (Since then, each degree of the nodes of the linegraph are also even). I'm asked to give (sufficing) conditions for a graph $...
- 851
3
votes
2
answers
466
views
Given a walk in a graph, find a path and an odd cycle contained in the trail.
Given this graph:
And given the $1-8$ walk
$$C_1=(1,3,2,3,4,5,3,6,7,6,8),$$
find a $1-8$ path.
Note: trails do not repeat edges, paths do not repeat vertices.
Lastly, given this closed odd-length ...
- 1,171
12
votes
3
answers
77k
views
Proving that a Euler Circuit has a even degree for every vertex
Theorem: Given a graph G has a Euler Circuit, then every vertex of G
has a even degree
Proof: We must show that for an arbitrary vertex v of G, v has a
positive even degree.
What does it ...
1
vote
1
answer
928
views
Dual of an eulerian graph
I was studying graph theory in Bollobas book's and I found a result given without proof that I wasn't able to understand. Here is my problem:
"Le G be an eulerian graph, then its planar dual is a ...
- 703
0
votes
2
answers
3k
views
Find an Eulerian path or circuit in a graph given its adjacency matrix
Consider the graph with adjacency matrix
\begin{pmatrix}
0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 &...
- 2,231
13
votes
2
answers
15k
views
Proof : cannot draw this figure without lifting the pen
This question maybe ridiculous but I always found it interesting... Here it is :
(I cannot put image so I put you the link of the pictures)
When I was in school I used to draw houses when I was bored :...
- 377