What is a spanning path in graph theory?

1.9k Views Asked by At

I was reading graph theory by Frank Harary and he mentioned that a maximal non-Hamiltonian graph will have every two vertex joined by a spanning path. Is a spanning path just another name for a Hamiltonian path?

2

There are 2 best solutions below

1
On BEST ANSWER

Yes. Page 11:

A spanning subgraph is a subgraph containing all the points of $G$

Therefore a spanning path is a path containing all the points of $G$, which is a Hamiltonian path.

0
On

In general given any graph $G=(V,E)$ a subgraph $H\subseteq G$ spans $G$ if and only if $V(H)=V(G)$. Therefore if $G$ contains a path graph $P$ we must have $V(P)=V(G)$ so the path runs through every vertex in $G$ and must be a hamoltonian path.