status: DONE
created: 2024-01-16T21:03
updated: 2024-06-11T01:14
discrete-mathematics-assignment-8
This graph is directed. Because the adjacency matrix is not symmetric
a)
It's clear that the graph is planar. it can be drawn in the plane without any edges crossing
b) It has Euler Circuit cause the thorem A connected multi-graph has an Euler circuit if and
only if each vertex has even degree. The vertex in the graph all has 4 edges. Therefore, it must have Euler Circuit.
c) It has Hamilton Circuits such that 1->2->3 ->4 ->5 ->6->1
Consider the following graph G = (V, E), where V = {1, 2, 3, 4} and E = {(1, 2), (2, 3), (3, 4), (4, 1), (1, 3)}.
This graph satisfies the condition that for any two non-adjacent vertices u and v in G,
For example, if we take u = 1 and v = 4, then
However, this graph does not have a Hamilton circuit.
Therefore, we have shown that the converse of Ore's theorem is false by providing a counterexample.