Question

Find connected graphs with at least eight vertices such that: (a) $G$ is Eulerian and not Hamiltonian. (b) $G$ is not Eulerian but is Hamiltonian. (c) $G$ is not Eulerian and not Hamiltonian. (d) $G$ is Eulerian and Hamiltonian.

Short answer

(a) Use repeating cycles, (b) Add a spike to a cycle, (c) Use a tree, (d) Use a regular 8-cycle.

Step-by-step solution

Understanding Eulerian and Hamiltonian Graphs

Eulerian graphs have circuits that include every edge exactly once, which means each vertex has an even degree. Hamiltonian graphs have a cycle that includes every vertex exactly once, without requiring all edges to be used.

Finding an Eulerian but not Hamiltonian Graph

To find a connected graph with at least 8 vertices that is Eulerian and not Hamiltonian, consider that it must have all vertices with even degrees but lack any cycle that uses all vertices. For instance, a graph structured like a repeating square with pairs of diagonal edges in a larger cycle ensure an Eulerian path but no single Hamiltonian path.

Constructing a Non-Eulerian but Hamiltonian Graph

Create a graph where not all vertices have even degrees to eliminate the possibility of it being Eulerian, yet the graph should have a cycle using all vertices. A simple cycle with an attached 'spike' makes it non-Eulerian but maintains a Hamiltonian cycle.

Building a Graph that is Neither Eulerian nor Hamiltonian

Design a graph where there are vertices of odd degree and no cycle can include all vertices. A simple tree structure satisfies both conditions: it is neither Eulerian (odd degrees allowed) nor Hamiltonian (no cycles possible).

Finding a Graph That Is Both Eulerian and Hamiltonian

This graph should both have even degrees for all vertices and contain a Hamiltonian cycle. A complete graph such as a cycle of 8 vertices (like a regular octagon) meets both conditions.

Key concepts

Eulerian Graphs

An Eulerian graph contains an Eulerian circuit, a path that starts and ends at the same vertex, using each edge exactly once. A key property of Eulerian graphs is that all vertices must have an even degree. This is because, at each step in the circuit, one enters and exits a vertex via a pair of edges.
When trying to identify or construct Eulerian graphs, ensure that every vertex has an even number of edges connected to it. This rule is essential for maintaining a smooth transition through each vertex without leaving any edges unused.
Understanding this concept helps in determining if a graph can host an Eulerian circuit, and is crucial when you are tasked to distinguish and create various graph types. Euler’s theorem helps here by clearly stating that a connected undirected graph is Eulerian if and only if every vertex of the graph has an even degree.

Hamiltonian Graphs

Hamiltonian graphs are fascinating because they contain a Hamiltonian cycle, a cycle that visits each vertex exactly once and returns to the starting vertex without needing to cover all edges. Unlike Eulerian graphs, Hamiltonian graphs have no specific degree conditions, making them more challenging to identify.
The existence of a Hamiltonian cycle in a graph can sometimes be predicted using Dirac's theorem, which states that a graph with at least three vertices is Hamiltonian if every vertex has a degree of at least $\frac{n}{2}$, where $n$ is the number of vertices. Yet, there are Hamiltonian graphs not satisfying these degree conditions, emphasizing the complexity of the concept.
The Hamiltonian graph exemplifies how vertex traversal without retracing steps through edges can be configured, which is a useful concept in optimization and network routing.

Connected Graphs

A graph is connected if there is a path between any pair of vertices. This means that in a connected graph, you can reach any vertex from any other vertex. Connectedness ensures the entire structure is accessible and without isolated sections.
In terms of damage to the structure, removing a vertex or an edge in a connected graph tends to have repercussions depending on the robustness (or redundancy) of the graph structure. For example, removing edges from a minimally connected, or tree structure, can quickly disconnect a part of the graph.
Designing or identifying connected graphs involves ensuring that enough edges exist to maintain a link between all vertices, essential for applications in real-world communication networks or logistical planning.

Vertex Degree

The vertex degree refers to the number of edges incident to a vertex in a graph. It is a fundamental aspect for classifying the properties of the graph, such as if it can be Eulerian.
Vertices with an even degree are crucial in forming Eulerian circuits, as they allow seamless traversal through the graph without leaving edges unused. On the other hand, graphs with vertices of various degrees require more analysis to determine properties like connectedness and potential cycles.
This concept is not just theoretical; understanding vertex degree is applicable in real-world scenarios such as modeling networks, circuits, and relationships where connection points (vertices) have limits on the number of connections they can sustain.