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
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
35
votes
11
answers
13k
views
How do I explain the Königsberg Bridge problem to a child?
I am going to demonstrate the Königsberg seven bridge problem in a science exhibition. I am also going to use a model for a more visual representation of the problem. Now, how do I explain this (the ...
- 10k
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 ...
9
votes
1
answer
21k
views
Euler path for directed graph?
How do we find Euler path for directed graphs? I don't seem to get the algorithm below!
Algorithm
To find the Euclidean cycle in a digraph (enumerate the edges in the cycle), using a greedy process,...
- 393
8
votes
2
answers
663
views
An ant walks on a cube over the diagonals of little cubes. Can it visit all little faces exactly once?
I have got this task at high-school math-contest seminar.
The theme is graphs.
Let us have $n \in \mathbb{N}$ and the cube $ n \times n \times n$. An ant can go over a diagonal of little cubes, but ...
- 1,359
8
votes
3
answers
22k
views
Prove that Petersen's graph is non-planar using Euler's formula
Prove that Petersen's graph is non-planar using Euler's formula.
I know that $n - m + f = 2$. But should I count $f$ and prove that the summation does not equal to two or solve to get $f =7$ and ...
- 83
7
votes
3
answers
9k
views
Sufficient condition for graph isomorphism assuming same degree sequence
We assume graph to be simple undirected.
In general, having the same degree sequence is not sufficient for two graphs to be isomorphic. A trivial example is a hexagon which is connected and two ...
- 8,820
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 ...
6
votes
1
answer
152
views
Is it possible to go over all lines of a grid with a pencil without lifting it or going over a drawn line?
Is it possible to go over all lines of an infinite grid with a pencil without lifting it or going over a drawn line ?
The pencil can cross through a segment already drawn but cannot go over an already ...
- 308
6
votes
1
answer
27k
views
How many Hamiltonian circuits are there in a complete graph with n vertices? [duplicate]
How many Hamiltonian circuits are there in a complete, undirected and simple graph with $n$ vertices?
The answer written in my book is: $$\frac{\left(n-1\right)!}{2}$$
What is the combinatorial ...
- 1,298
6
votes
1
answer
1k
views
A connected simple graph $G$ has $14$ vertices and $88$ edges. Prove $G$ is Hamiltonian, but not Eulerian.
A connected simple graph $G$ has $14$ vertices and $88$ edges. Prove $G$ is Hamiltonian, but not Eulerian.
I almost feel like you have to prove these two parts separately. I understand that to be ...
- 303
6
votes
1
answer
206
views
Properties of prime sum graphs
The prime sum graph $P_n$ on the vertex set $V = \{1,\dots, n\}$ has an edge $e = xy$ when $x+y$ is prime. It is easy to show that any such $P_n$ is bipartite (put odd numbers in one part and evens in ...
- 1,919
5
votes
3
answers
12k
views
Is it possible disconnected graph has euler circuit?
I have doubt !
Wikipedia says :
An Eulerian graph is one in which all vertices have even degree;
Eulerian graphs may be disconnected.
What I know :
Defitition of an euler graph
"An Euler ...
- 4,785
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