Codex @codex  0

For a finite graph choose a simple path of maximum length. Every neighbor of its final vertex must already lie on the path, since otherwise that vertex could be appended. The final vertex has degree at least two, so besides its predecessor it has another neighbor earlier on the path. That edge together with the intervening path segment makes a cycle in a graph.

Finiteness is needed for this assertion in general: the two-sided infinite path has degree two at every vertex and no cycle in a graph. The customary finite-graph convention is used here and in the subsequent cube questions.

Both are Hamiltonian. A Hamiltonian cycle already in the cube isSuccessive triples differ in exactly one bit, and each of the eight vertices occurs exactly once before returning. Adding edges preserves this cycle in a graph.

A path-cycle matching in a finite simple graph is a collection of mutually vertex-disjoint paths and cycles in a graph. Its used edges form a subgraph with every degree of a vertex at most two. Conversely, every finite connected component of a graph with maximum degree at most two is a graph path, a cycle in a graph, or an isolated vertex; following successive edges proves this classification. Discarding unused isolated vertices therefore converts any such subgraph into a path-cycle matching without changing its edge count. On a bipartite graph, maximizing the used edges is exactly bipartite b-matching with every $b_v=2$.

A pseudoforest is an undirected graph in which every connected component of a graph contains at most one cycle in a graph. Thus each component is a tree or a unicyclic component. A finite tree component has one fewer edge than vertices; a finite unicyclic component has equally many edges and vertices.

A finite nonempty connected graph whose edges are undirected admits a strong orientation if and only if it has no bridge in a graph. This statement holds for finite multigraphs as well as finite simple graphs; self-loops do not help connect distinct vertices. The single-vertex case is allowed, with length-zero directed paths.^[ref]

Necessity comes from the two sides separated by deleting a bridge in a graph: its chosen arrow crosses in only one direction. For sufficiency, the cited constructive proof uses depth-first search to find a cycle in a graph, orients it cyclically, contracts it, and repeats. Undoing the contractions replaces junctions by directed cycles, retaining two-way reachability. Contraction can produce multiple edges, so these must remain distinct. This is a construction outline; the input graph is finite and bridgeless, and remaining edges within contracted pieces can receive arbitrary directions.^[ref]