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.
21
questions
7
votes
2
answers
4k
views
Does Eulerian cycle in digraph really need strongly connected component?
I read that a directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree, and all of its vertices with nonzero degree belong to a single strongly connected ...
1
vote
1
answer
688
views
Connected graph with colored edges
We have connected undirected graph with colored edges in two way (green or blue). And also each vertex have the same number of green and blue edges. How to prove that there are alternate colored (...
- 350
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
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 ...
5
votes
2
answers
6k
views
Prove that the graph dual to Eulerian planar graph is bipartite.
How would I go about doing this proof I am not very knowledgeable about graph theory I know the definitions of planar and bipartite and dual but how do you make these connection
- 6,708
3
votes
1
answer
840
views
Number of spanning arborescences does not depend on $i$.
Let $G$ be a directed graph with vertices $x_1,x_2,\dotsc, x_n$ for
which a directed Eulerian circuit exists. A spanning arborescence with
root $x_i$ is a spanning tree $T$ of $G$, with root $x_i$,...
- 8,656
0
votes
1
answer
1k
views
Bipartite graph. average degree. Euler circuit. [closed]
This is such a hard question to get my head around. Can anyone help solve this?
- 287
37
votes
12
answers
134k
views
Is it possible to draw this picture without lifting the pen?
Some days ago, our math teacher said that he would give a good grade to the first one that will manage to draw this:
To draw this without lifting the pen and without tracing the same line more than ...
- 641
4
votes
1
answer
3k
views
Graph $G$ has k vertices of odd degree, prove there is $\dfrac{k}{2}$ non-closed trails that cover all the edges of the graph exactly once.
A graph $G$ has k vertices of odd degree, prove that there is $\dfrac{k}{2}$ non-closed trails on the graph that cover all the edges of the graph exactly once.
Here is my proof:
The graph has $k$ ...
- 1,535
1
vote
2
answers
87
views
Property of a connected graph with $\text{deg(all nodes)}=\text{even}$
In my lecture nodes it is proposed that for a connected graph $G$ with the degree of all nodes being even, there exist two paths between any two nodes $x,y\in G$ with no common edges. From the very ...
- 175
1
vote
3
answers
2k
views
Does this graph have Eulerian circuit paths?
For this graph, do Eulerian circuit path exist or not?
Basic definition A Euler circuit is a circuit that uses every edge of a graph
exactly once. A Euler circuit starts and ends at the same vertex.
...
- 187
1
vote
2
answers
906
views
Proof - a vertex in a path has an even number of edges [duplicate]
Given a simple undirected graph,
let's say we have a path of i edges that can repeat nodes but not edges
i.e. nodes may come up more than once in the path but not the edges.
NOTE : I never said ...
- 199
1
vote
1
answer
1k
views
Proof of existance of Eulerian cycle in directed graph
Claim
A directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree, and all of its vertices with nonzero degree belong to a single strongly connected ...
- 1,189
1
vote
1
answer
2k
views
Planar graph has an euler cycle iff its faces can be colored with 2 colors
Planar graph has an euler cycle iff its faces can be properly colored with 2 colors (such way the colors of two faces that has the common edge are different).
I have an idea to consider the dual ...
- 740
1
vote
2
answers
366
views
Generalization of Euler Circuits that Visit Each Edge $k$-times
It is known that a graph has an Eulerian circuit if and only if each node has even degree. Two questions: (1) What is the term used to describe a cycle (if the right term) that visits each edge in a ...
- 14.7k