0
$\begingroup$

Definitions:

$\Delta(G)$ : maximum degree of graph $G$

$\beta_0(G)$ : maximum number of independent vertices (vertices not sharing an edge)

Show that $\Delta(G) \leq \beta_0(G)$ if $G$ is simple and has no triangles.

Induction:

$|V(G)| = 3$ :

Assume the graph with degree sequence $(2,1,1)$. If $G$ is the realization of this sequence then it has no triangles and $\Delta(G) \leq \beta_0(G)$.

$|V(G)| = k$ :

We assume that $G$ has no triangles and $\Delta(G) \leq \beta_0(G)$.

$|V(G)| = k + 1$ :

The new vertex cannot share an edge with two adjacent vertices (because a triangle would be formed). Does this ensure that if this new vertex increases $\Delta(G)$ by one then it will increase $\beta_0(G)$ by one for the inequality to still hold?

Any hint would be appreciated.

$\endgroup$

1 Answer 1

1
$\begingroup$

`Does this ensure that if this new vertex increases $\Delta(G)$ by one then it will increase $\beta _0(G)$ by one for the inequality to still hold?'

No not necessarily. Consider for your graph of order $k$ the tree $G_k$ formed by taking a single edge $ab$, and two sets $A$ and $B$ each with 5 vertices. Make all of $A$ adjacent to $a$, and all of $B$ adjacent to $b$. Now get your order $k+1$ graph $G_{k+1}$ by adding a new vertex $c$, and making $c$ adjacent to all of $A$, and to the vertex $b$.

In $G_k$, $A\cup B$ is a maximal independent set, and still is in $G_{k+1}$.


Here's a hint for the question though. Don't use induction, and let $v$ be a vertex of maximum degree in $G$. What can you say about the set of all neighbours of $v$?

$\endgroup$
1
  • $\begingroup$ Thanks for the hint. It was way simpler after all. $\endgroup$
    – Andrew
    Commented Apr 16, 2020 at 10:23

You must log in to answer this question.

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