One graph a subgraph of another? Consider a graph G on n vertices with minimum degree delta and with its largest independent set a>delta. Consider the graph bar KaotimesKn−a−1 (in other words, take a set of a points and add every edge relation between that set and Kn−a−1. Intuitively, this graph is a Kn−1 with a missing Ka). How does one prove that that no matter how I take a vertex v and connect it to δ vertices in the bar Ka, I will always get a copy of G.

Elena Simmons

Elena Simmons

Open question

2022-08-27

One graph a subgraph of another?
Consider a graph G on n vertices with minimum degree δ and with its largest independent set a > δ. Consider the graph K ¯ a K n a 1 (in other words, take a set of a points and add every edge relation between that set and K n a 1 . Intuitively, this graph is a K n 1 with a missing K a ).
How does one prove that that no matter how I take a vertex v and connect it to δ vertices in the K ¯ a , I will always get a copy of G.
I think this is trivially true for bipartite graphs, but I dont know how to prove it in general. Any help is nice!

Answer & Explanation

kwizerwa3w

kwizerwa3w

Beginner2022-08-28Added 4 answers

It's not true. Consider a star.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?