Return to Answer

Let $k=5$. Then there is a graph $G$ such that:

1. $G$ is formed by $5$ cliques of order $5$, with any two cliques sharing at most one point in common.
2. $G$ has an induced subgraph $H$ such that every vertex in $H$ has degree at least $5$ in $H$.

So for this example, the Szekeres-Wilf Theorem cannot be used to show that $G$ is $5$-colorable.

Here is the example:

I've drawn five pentagons, three in black, one red, and one blue. Any two pentagons share exactly one point in common. Let $G$ be the graph obtained by filling in the rest of the edges to that the pentagons become cliques of order $5$. Let $H$ be subgraph induced on the nine green vertices. Every vertex in $H$ has degree at least $5$ in $H$.

EDIT: Here is a picture of the induced graph $H$. I think I got all the edges, but there are at least enough to show that every vertex in $H$ has degree at least $5$.

Let $k=5$. Then there is a graph $G$ such that:

1. $G$ is formed by $5$ cliques of order $5$, with any two cliques sharing at most one point in common.
2. $G$ has an induced subgraph $H$ such that every vertex in $H$ has degree at least $5$ in $H$.

So for this example, the Szekeres-Wilf Theorem cannot be used to show that $G$ is $5$-colorable.

Here is the example:

I've drawn five pentagons, three in black, one red, and one blue. Any two pentagons share at most one point in common. Let $G$ be the graph obtained by filling in the rest of the edges to that the pentagons become cliques of order $5$. Let $H$ be subgraph induced on the nine green vertices. Every vertex in $H$ has degree at least $5$ in $H$.

EDIT: Here is a picture of the induced graph $H$. I think I got all the edges, but there are at least enough to show that every vertex in $H$ has degree at least $5$.

Let $k=5$. Then there is a graph $G$ such that:

1. $G$ is formed by $5$ cliques of order $5$, with any two cliques sharing at most one point in common.
2. $G$ has an induced subgraph $H$ such that every vertex in $H$ has degree at least $5$ in $H$.

So for this example, the Szekeres-Wilf Theorem cannot be used to show that $G$ is $5$-colorable.

Here is the example:

I've drawn five pentagons, three in black, one red, and one blue. Any two pentagons share exactly one point in common. Let $G$ be the graph obtained by filling in the rest of the edges to that the pentagons become cliques of order $5$. Let $H$ be subgraph induced on the nine green vertices. Every vertex in $H$ has degree at least $5$ in $H$.

Let $k=5$. Then there is a graph $G$ such that:

1. $G$ is formed by $5$ cliques of order $5$, with any two cliques sharing at most one point in common.
2. $G$ has an induced subgraph $H$ such that every vertex in $H$ has degree at least $5$ in $H$.

So for this example, the Szekeres-Wilf Theorem cannot be used to show that $G$ is $5$-colorable.

Here is the example:

I've drawn five pentagons, three in black, one red, and one blue. Any two pentagons share exactly one point in common. Let $G$ be the graph obtained by filling in the rest of the edges to that the pentagons become cliques of order $5$. Let $H$ be subgraph induced on the nine green vertices. Every vertex in $H$ has degree at least $5$ in $H$.

EDIT: Here is a picture of the induced graph $H$. I think I got all the edges, but there are at least enough to show that every vertex in $H$ has degree at least $5$.

For $k=5$ it is possible to construct a graph $G$ as above which contains an induced subgraph $H$ with the property that every vertex in $H$ has degree at least $5$ in $H$. So this shows that the Szekeres-Wilf Theorem won't suffice to show that $G$ is $5$-colorable.

Here is the example:

I've drawn five pentagons, three in black, one red, and one blue. Every two pentagons share exactly one point in common. So $G$ is the graph obtained by filling in the rest of the edges to that the pentagons become $5$-cliques. Now let $H$ be subgraph induced on the nine green vertices. Every vertex in $H$ has degree at least $5$ in $H$.

Let $k=5$. Then there is a graph $G$ such that:

1. $G$ is formed by $5$ cliques of order $5$, with any two cliques sharing at most one point in common.
2. $G$ has an induced subgraph $H$ such that every vertex in $H$ has degree at least $5$ in $H$.

So for this example, the Szekeres-Wilf Theorem cannot be used to show that $G$ is $5$-colorable.

Here is the example:

I've drawn five pentagons, three in black, one red, and one blue. Any two pentagons share exactly one point in common. Let $G$ be the graph obtained by filling in the rest of the edges to that the pentagons become cliques of order $5$. Let $H$ be subgraph induced on the nine green vertices. Every vertex in $H$ has degree at least $5$ in $H$.