proving that graph G is a path

Question

I want to prove that the connected graph $G$ with $\delta(G) = 1$ and each vertex has a degree of $1$ or $2$, is a path. Can you tell whether my proof is correct?

Since $G$ is connected, there is a path between all of its vertices. Suppose that $u_1,\dots,u_i,\dots,u_n$ is a path from $u_1$ to $u_n$ which contains all vertices.

According to the assumption, there could not be a cycle in this path; because if there be a cycle, the degree of one vertex should be greater than $2$ and it's in contrast with the assumption. So the graph $G$ is a path.

Answer 1

We can make your proof work if we choose $u_1$ and $u_n$ carefully, but it does not work out of the box. Two problems:

• We cannot assume that a path exists which includes all vertices; we're going to have to pick a path in some other way, then prove that it has this property.
• There are plenty of paths that don't include all vertices, so if we're going to be proving this about our path, we want to pick the right path to start with.

So here is how we find the path instead. Since $\delta(G)=1$ there is a vertex of degree $1$. The total number of odd-degree vertices in a graph must be even, so there must be at least one more vertex of degree $1$. Let $s, t$ be two vertices of degree $1$; since $G$ is connected, there is a path $u_1, u_2, \dots, u_n$ with $u_1 = s$ and $u_n = t$.

We know that

• $u_1$ and $u_n$ are incident to $1$ edge of the path, and they have degree $1$, so they have no other edges.
• $u_i$ for $1 < i < n$ is incident to $2$ edges of the path, and it cannot have degree more than $2$, so it has no other edges.

So there are no edges out of $u_1, \dots, u_n$ other than the edges of the path. Since $G$ is connected, there cannot be any other vertices (they would have no way to get to vertices on this path). Therefore the path contains all the vertices and edges of the graph.

Answer 2

You stated

Suppose that $u_1,...,u_i,...u_n$ is a path from $u_1$ to $u_n$ which contains all vertices.

You cannot assume that such a path exist. Suppose that $G$ is path $v_1v_2\ldots v_n$. Then there is not path from $v_2$ to $v_{n}$ that pass by $v_1$.

you should reason by induction $n$ the number of vertices of $G$

1. if $n=1$ or $n=2$, $G$ is trivially a path
2. Suppose that the statement if true for any graph of order $n\geq 2$. Let $G$ be a connected graph on $n+1$ vertices satisfying the conditions $\delta=1$ and $\Delta\leq 2$. Let $u$ be a vertex of degree 1. $u$ has a unique neighbour $v$ in $G$. As $|V(G)|=n+1>2$, and $G$ is connected, then $v$ has degree 2 in $G$.

Let $H=G\backslash\{u\}$ be the graph $G$ after removing $u$. Then $H$ has order $n$, and in $H$, $v$ has degree 1. Therefore $H$ satisfy the conditions : $\delta_H=1$, $\Delta_H\leq 2$. By induction $H$ is a path, and because $G$ is $H$ adding a neighbour to a vertex of degree 1 (the leaf $v$) then so is $G$.