All Questions
Tagged with eulerian-path proof-writing
6
questions
0
votes
0
answers
73
views
Prove by induction on the length of the walk that whenever it visits a vertex, it has traversed an odd number of edges incident to it
Say we walk on a finite, connected, even-degree graph with no self loops in the following way: we start from an arbitrary vertex $s \in V$, at each step choosing an untraversed edge incident to the ...
- 3,019
-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
0
votes
1
answer
448
views
How do I write a proof that $G^C$ (G complement) has a Euler cycle in a general way?
So I'm basically failing my discrete mathematics class, with Graph Theory, because I don't know how to define something generally and not specifically, and all our teacher does is read the textbook ...
- 19
0
votes
1
answer
617
views
Any graph with an Euler circuit is connected.
So I started with defining an Euler circuit as a closed walk containing at least one edge, not repeating any edge, and ending the walk on the same vertex as it was started. Is this a full proof, ...
- 57
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
0
votes
1
answer
161
views
Graph theory cycle problems
Question background: In each of the pictures below; there are line segments connecting black dots (7 line segments in the left picture and 12 line segments in the right picture).
Question asks to ...
- 125