Waste less time on Facebook — follow Brilliant.
×

Basic Graph Theory Question

Prove that if there exists a path on a graph that is both Hamiltonian and Eulerian, then the graph is either cyclic or linear.

Details and Assumptions

A Hamiltonian Path is a path that goes through all vertices exactly once.

An Eulerian Path is a path that goes through all edges exactly once.

Note by Daniel Liu
2 years, 9 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

At first let's assume that such a path \(P\) exists on some graph \(G\). Now we know that \(G\) is Eulerian. So, we will travel through all the edges. So if vertex has degree greater than \(2\) then, we will have to land on it more than once. Because, no matter how we travel if that vertex is not our starting point, then we have to 'enter' it using one edge and leave using another. Since, it has more edges going in to it we will have to enter it once more and thus it won't Hamiltonian and if it is the 'starting point', then we would use one edge to leave from it and anther enter it if it is our finishing point as well (We can't leave from from our starting point if we land on it for the second time because otherwise it won't be Hamiltonian). This is our key argument.

Now, since we know that our path is Eulerian we can divide them into to classes.

\(1)\) The Eulerian Circuits

\(2)\) and The Eulerian non-circuits

Our path will be an Eulerian circuit when the degree of all the vertices are even( in this case\(2\)). So, this would form a cycle.

If our path doesn't form a circuit it means that two vertices will have odd degrees and in this case \(1\) and since our
path is connected, the degree of all the other vertices are \(2\). And since the graph is connected only the starting point and the terminal point can have odd degrees. So, we can say that this path is linear. Siam Habib · 2 years, 9 months ago

Log in to reply

Here's my attempt at proof:

Assume a path \(P\) exists on a graph \(G\) that is both Hamiltonian and Eulerian. Let \(P\) be labeled \(v_1e_1v_2e_2v_3\cdots e_{n-1}v_n\) with alternating vertices and edges. Since \(P\) contains all of the graph's vertices and edges, a path between any two vertices can be made, and therefore \(G\) is connected. Note that all the vertices and edges are distinct too, except for the first and last vertices may be the same. Now we have two cases.

Case 1: \(v_1\neq v_n\) We have \(n-1\) edges and \(n\) distinct vertices in \(G\). Just from the information given by \(P\), the interior vertices of \(P\) have at least degree \(2\) (they have two edges coming from them) and the two exterior vertices of \(P\) have at least degree \(1\). Since each edges has two vertices on it, we can calculate the number of edges from this information: the number of edges must be at least \((2(n-2)+2)/2 = n-1\). Since this is exactly the number of edges in \(G\), the interior vertices of \(P\) have degree \(2\) and the two exterior vertices have degree \(1\). The only connected graph with this property is a linear graph (does this statement need more rigor?).

Case 2: \(v_1 = v_n\) We have \(n-1\) edges and \(n-1\) distinct vertices in \(G\). Using the same argument as above, since each vertex has at least degree \(2\), the number of edges (counting this way) is at least \(2(n-1)/2 = n-1\), which is exactly the number of edges we already have. Thus each vertex has degree \(2\). The only connected graph with this property is a cyclic graph (again, more rigor?). Bob Krueger · 2 years, 9 months ago

Log in to reply

I thought a path that goes through all the edges exactly once is called Eulerian. Siam Habib · 2 years, 9 months ago

Log in to reply

@Siam Habib Thanks, edited. Daniel Liu · 2 years, 9 months ago

Log in to reply

It could also be a Lollypop graph. Abhishek Sinha · 2 years, 9 months ago

Log in to reply

@Abhishek Sinha Can you explain what a lollipop graph looks like?

EDIT: I searched it up. Can you explain how it can be a lollipop graph? I can't seem to find a path that is both hamiltonian and eulerean. Daniel Liu · 2 years, 9 months ago

Log in to reply

@Daniel Liu Start at the tail and go around the head, so long as you don't require your paths to end on a vertex. Bob Krueger · 2 years, 9 months ago

Log in to reply

@Bob Krueger paths are defined to start and end at a vertex (at least that's what I thought) so... Daniel Liu · 2 years, 9 months ago

Log in to reply

@Daniel Liu By a lollipop graph, I mean a cycle and a line joined together at a vertex. Abhishek Sinha · 2 years, 9 months ago

Log in to reply

@Abhishek Sinha I don't think that it can be a lollipop graph. A Hamiltonian path is a path is a path that goes through all the vertices exactly once unless it is a circuit. On that case, only one vertex gets to be visited twice, the starting point.

In a lollipop, if you start from the bottom of the line, your path will have to end at the the point on the cycle which is adjacent to the line.

So on that case, you traveled to that vertex twice. But, that path is not a circuit. So, you can't travel through one vertex twice. So, it is not Hamiltonian.

If you start from the point on the cycle that is adjacent to the line, then you would still go through the starting point twice. But the path isn't a circuit as stated earlier. So, still the path is not Hamiltonian.

Follow the images:

lollipop graphs

lollipop graphs

My key argument is that a Hamiltonian path can pass through only one vertex twice if and only if the path is a Hamiltonian Circuit. A lollipop is not a circuit. So, a lollipop is not Hamiltonian. Siam Habib · 2 years, 9 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...