All Questions
Tagged with eulerian-path graph-connectivity
10
questions
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
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
0
votes
2
answers
1k
views
Determine if edge is a bridge in a graph
I would like to implement Fleury’s algorithm to find Eulerian trails in a graph. This algorithm requires me to tell if a given edge is a cut edge (bridge).
Is there a more effective way of doing this ...
2
votes
2
answers
841
views
Is Eulerian graph necessarily connected?
If a graph is Eulerian (i.e. has an Eulerian tour), then do we immediately assume for it to be connected?
The reason I ask is because I came across this question:
Graph and its line Graph that both ...
- 467
3
votes
2
answers
1k
views
Eulerian graph has three vertices of the same degree
Let $G$ be a connected graph with $n \ge 3$ vertices.
Prove that if $G$ has an Euler Cycle than it has 3 vertices of the same degree.
I thought using the Pigeonhole principle but I'm not sure how...
...
- 227
1
vote
2
answers
53
views
Proving the graph $V=\{S\subset\{1,2\ldots9\}\mid3\leq\left|S\right|\leq4\},\,\,\,E=\{(u,v)\mid u\subset v\}$ is connected
Let $G=\left\langle V,E\right\rangle$ be an undirected graph with $V=\left\{ S\subset\left\{ 1,2,\ldots,9\right\} \mid\left|S\right|\in\left\{ 3,4\right\} \right\}$ and $E\left\{ \left(u,v\right)\mid ...
- 1,546
0
votes
0
answers
287
views
Alternating path from any vertex to any vertex [duplicate]
Statement: Given a connected graph with all edges coloured in one of two colours (red and black), so that for each vertex the number of incident red edges is equal to the number of black edges.
Proof:...
0
votes
1
answer
105
views
Question on graph Connectivity.
Question
Consider the statement below-:
$\text{1.In simple graph with 6 vertices,if degree of each vertex is 2 ,then graph is connected}$
$\text{2.In simple graph with 6 vertices,if degree of each ...
- 2,540
1
vote
0
answers
57
views
Removing path of a connected graph. [duplicate]
I bumped into this question in an old exercice sheet :
Let $ G = (V,E) $ be a connected graph with minimum degree $ \delta(G) = k \geq 2$. Prove that there exist a path $P = x_1x_2...x_k$ such that ...
- 153
2
votes
1
answer
1k
views
The line graph of Eulerian and Hamiltonian graphs
If a graph $G$ is Eulerian then I can show that the line graph of $G$ is Eulerian but is the converse true ?
If $G$ is Hamiltonian then I can show that the line graph of $ G$ is Hamiltonian but is ...
- 285