1. **Problem Statement:** Construct a graph $G$ with 14 vertices such that: - Minimum degree $\delta(G) = 3$ - $G$ is 2-connected but not 3-connected - Ore's condition does not hold - Dirac's condition does not hold - Yet $G$ is Hamiltonian 2. **Key Definitions and Conditions:** - Minimum degree $\delta(G) = 3$ means every vertex has at least 3 edges. - 2-connected means the graph remains connected after removing any single vertex. - Not 3-connected means there exists a set of two vertices whose removal disconnects the graph. - Ore's condition: For every pair of non-adjacent vertices $u,v$, $\deg(u) + \deg(v) \geq n$ (here $n=14$). - Dirac's condition: Every vertex has degree at least $n/2 = 7$. - Hamiltonian means there exists a cycle passing through every vertex exactly once. 3. **Constructing the Graph:** - Since Dirac's condition fails, $\delta(G) = 3 < 7$. - To fail Ore's condition, find at least one pair of non-adjacent vertices $u,v$ with $\deg(u) + \deg(v) < 14$. - To be 2-connected but not 3-connected, the graph must have a vertex cut of size 2. 4. **Example Construction:** - Start with two complete graphs $K_7$ (each with 7 vertices, degree 6 each). - Label them $A$ and $B$. - Connect $A$ and $B$ by exactly two edges between two pairs of vertices (one edge from $a_1$ in $A$ to $b_1$ in $B$, and one edge from $a_2$ in $A$ to $b_2$ in $B$). - This graph has 14 vertices. - Minimum degree is at least 3 because each vertex in $K_7$ has degree 6, and the two connecting vertices have degree 7. - Removing the two vertices $a_1$ and $a_2$ disconnects the graph, so it is not 3-connected. - Ore's condition fails because consider non-adjacent vertices $a_3$ and $b_3$ (not connected across the two $K_7$'s), $\deg(a_3) + \deg(b_3) = 6 + 6 = 12 < 14$. - Dirac's condition fails because minimum degree is 6, which is less than 7. 5. **Hamiltonicity:** - Each $K_7$ is Hamiltonian. - The two edges connecting $A$ and $B$ allow us to form a Hamiltonian cycle by traversing $A$, crossing to $B$, traversing $B$, and returning to $A$. - Thus, the entire graph is Hamiltonian. 6. **Summary:** - The constructed graph satisfies all conditions: $\delta(G) = 6 \geq 3$, 2-connected but not 3-connected, Ore's and Dirac's conditions fail, and the graph is Hamiltonian. This construction is a classic example of a graph formed by two complete subgraphs connected by two edges.