Problem 58 - Discrete Mathematics with Applications

Question

Give an example of a graph that is: Neither Eulerian nor Hamiltonian.

Step-by-Step Solution

Answer

A graph with 5 vertices forming a shape similar to a pentagon with an extra edge connecting two non-adjacent vertices can serve as an example of a graph that is neither Eulerian nor Hamiltonian: ```plaintext 1 --- 2 | / \ 5 -- 4 -- 3 ``` Adjacency list: 1: 2, 5 2: 1, 3, 4 3: 2, 4 4: 2, 3, 5 5: 1, 4 Vertices 2 and 4 have an odd degree, preventing the graph from being Eulerian. Additionally, no Hamiltonian cycle can be formed, as it is not possible to visit vertex 5 without visiting either vertex 1 or 4 twice.

Step 1: Consider a base graph

Let's consider a simple graph with 5 vertices and form a shape similar to a pentagon with an extra edge connecting two non-adjacent vertices. Illustrating this graph as follows: 1 --- 2 | / \ 5 -- 4 -- 3 We can represent this graph with this adjacency list: 1: 2, 5 2: 1, 3, 4 3: 2, 4 4: 2, 3, 5 5: 1, 4 Now we will analyze this graph to check whether it is Eulerian or Hamiltonian.

Step 2: Check for Eulerian graph condition

To check if the graph is Eulerian, we need to ensure that all vertices have even degree. From our adjacency list, we can see the degree of each vertex: 1: degree 2 2: degree 3 3: degree 2 4: degree 3 5: degree 2 We can observe that vertices 2 and 4 have an odd degree, so the graph is not Eulerian.

Step 3: Check for Hamiltonian graph condition

For a graph to be Hamiltonian, there must be a Hamiltonian cycle. However, finding a Hamiltonian cycle can be difficult, and there is no simple condition to check like the Eulerian graphs. In this case, we can manually search for a Hamiltonian cycle by looking for a path that visits every vertex exactly once and returns to the starting vertex. No matter how we visit the vertices, we will not be able to find a Hamiltonian cycle because it will not be possible to visit vertex 5 without visiting either vertex 1 or 4 twice. For example, if we start at vertex 1, we can only move to vertex 2 next and then to vertices 3 and 4 in any order. After visiting vertices 3 and 4, we will be forced to visit either vertex 1 or 4 again, violating the Hamiltonian condition. Therefore, this graph is neither Eulerian nor Hamiltonian.

Key Concepts

Eulerian Graph

An Eulerian graph is one where you can find an Eulerian circuit, meaning a path that visits every edge exactly once and returns to the starting vertex. This concept is named after the Swiss mathematician Leonhard Euler. Eulerian graphs have some distinct features:

• All vertices must have an even degree.
• If a graph is connected and all its vertices have even degree, it is Eulerian.
• A graph can also be considered semi-Eulerian if it has exactly two vertices of odd degree, in which case there is an Eulerian trail (not a circuit).

A perfect example of an Eulerian graph is a circle where every point or intersection is connected to two other points.
Keep in mind that checking for all vertices to have even degrees is a quick way to test if a graph is Eulerian.

Hamiltonian Graph

A Hamiltonian graph involves a Hamiltonian cycle, which is a path that visits every vertex exactly once before returning to the starting vertex. Unlike Eulerian graphs, there is no straightforward rule to determine if a graph is Hamiltonian, which makes this concept a bit more challenging.

• One way to explore if a graph is Hamiltonian is by visually inspecting potential cycles.
• Unlike Eulerian graphs, there's no need to visit every edge, just every vertex exactly once.
• Hamiltonian cycles are named after Sir William Rowan Hamilton, who studied these paths in the 19th century.

To check if a graph is Hamiltonian manually, you can try tracing different cycles to see if they meet the Hamiltonian criteria. Graphs like triangles, which naturally form a cycle, are clear examples of Hamiltonian graphs.

Degree of a Vertex

The degree of a vertex in a graph indicates how many edges connect to it. Each connection or edge counts towards the vertex's degree.

• If a vertex connects to three other vertices, it has a degree of three.
• Degrees can either be even or odd, which can impact whether a graph is Eulerian.
• To find the degree of any vertex, you can count the number of lines or connections stemming from it.

Understanding the degree of a vertex helps in determining the nature of the graph itself. For instance, in Eulerian graphs, all vertices must have even degrees. Meanwhile, in understanding connectivity and structure, degrees give insight into how complex a graph is.