0
$\begingroup$

Show that if $G$ is a connected graph such that the degree of every vertex is one of 3 distinct number and each of these three number is degree of at least one vertex of $G$, then there is a path in $G$ contain three vertices whose degree are distinct.

I tried to let $a,b,c$ ($a,b,c \geq 1$) be the number of vertices of degree $x,y,z$ respectively for $x,y,z$ are distinct. The book told me that I need to consider the path that contain 2 vertices of distinct degree. But I don't understand how this could help me. Can anyone enlighten me please?

$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Let $X$ be a vertex of degree $x$. Let $P_y$ be a shortest path from $X$ to a vertex of degree $y$ and $P_z$ be a shortest path from $X$ to a vertex of degree $z$. If $P_y$ uses a vertex of degree $z$, or $P_z$ uses a vertex of degree $y$, then we've found the required path.

So we can assume that $P_y=(X,X_1,\ldots,X_k,Y)$ for vertices $X_i$, each of degree $x$, and a vertex $Y$ of degree $y$. Similarly, $P_z=(X,X_1^\prime,\ldots,X_m^\prime,Z)$ for vertices $X_i^\prime$ of degree $x$ and a vertex $Z$ of degree $z$.

Now, what can you do if $P_y\cap P_z=X$? What can you do if $X_i=X_{j}^\prime$ for some $i,j$?

$\endgroup$
4
  • $\begingroup$ if $P_y \cap P_x =X$ then we found a path contain 3 vertices with distinct degree. And same thing happen if we have $X_i = X_j'$. But how can we guarantee that these thing will happen. What if $P_y \cap P_z \not = X$ and $ X_i \not = X_j$ for every $i,j$? Does this lead to contradiction some how? $\endgroup$
    – Diane Vanderwaif
    Sep 17, 2014 at 12:32
  • $\begingroup$ @CalvinLin Do you mean the first line in the second paragraph? Your example was dealt with in the last sentence of the first paragraph. I don't think there is a requirement that the path has exactly $3$ vertices, just that it contains $3$ vertices of differing degrees. Perhaps Diane will clarify this point. $\endgroup$
    – Casteels
    Sep 17, 2014 at 12:44
  • $\begingroup$ @Casteels Ah, I see. I interpreted that sentence differently, thinking it was path of exactly 3 vertices. $\endgroup$
    – Calvin Lin
    Sep 17, 2014 at 12:45
  • $\begingroup$ @DianeVanderwaif At least we know $X\subseteq P_y\cap P_z$. The trouble is the two paths may intersect elsewhere, and a path should not have repeated vertices. But in this case, you can still find a path from $Y$ to $Z$, just one that doesn't use $X$. It might help to draw some examples, e.g., something that looks like an $\alpha$ or $\lambda$. $\endgroup$
    – Casteels
    Sep 17, 2014 at 12:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .