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.

#Algebra #GraphTheory #HamiltonianWalk #Pathwalking #EuclideanWalk

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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 - 6 years, 12 months ago

It could also be a Lollypop graph.

Abhishek Sinha - 7 years ago

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 - 7 years ago

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 - 7 years ago

@Bob Krueger – paths are defined to start and end at a vertex (at least that's what I thought) so...

Daniel Liu - 7 years ago

By a lollipop graph, I mean a cycle and a line joined together at a vertex.

Abhishek Sinha - 7 years ago

@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

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 - 7 years ago

I thought a path that goes through all the edges exactly once is called Eulerian.

Siam Habib - 7 years ago

Thanks, edited.

Daniel Liu - 7 years ago

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 - 7 years ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$