# Maximum degree less or equal to the cardinality of a maximal independent set

## 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.

`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$$?