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$
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$
  • $\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 '14 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 '14 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 '14 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 '14 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.