in Others edited by
18 views
0 votes
0 votes

Given a graph $G$ and a vertex $u$ in it, let $N(u)$ denote the set of neighbours of $u$ in $G$. A graph $G$ having $n$ vertices is said to be $k$ degenerate if there is a linear ordering $v_{1}, v_{2}, \ldots, v_{n}$ of the vertices, in which each vertex has at most $k$ neighbours after it. That is, for all $i \in\{1,2, \ldots, n\},\left|\left\{v_{j} \in N\left(v_{i}\right): j>i\right\}\right| \leq k$.

  1. Calculate the maximum number of edges possible in a $k$-degenerate graph having $n$ vertices.
  2. Let $H$ be any graph. Let $H^{\prime}$ be the graph obtained by removing a vertex of degree at most $k$ from $H$. Prove that $H$ is $k$-degenerate if and only if $H^{\prime}$ is $k$-degenerate.
in Others edited by

Please log in or register to answer this question.

Related questions