0
$\begingroup$

Let $P_n$ denote a path on $n$ vertices; $C_n$ denote a cycle on n vertices. Let $G$ be a connected simple graph that does not have $P_4$ or $C_4$ as an induced subgraph. Prove that $G$ has a vertex adjacent to all other vertices.

I'm thinking if I take a vertex of maximum degree, and then proving that that vertex must be adjacent to all other vertices, but I'm not sure how to show that just by knowing that there's no 4-cycle and there's no path with just 4 vertices. How is that even possible on a connected graph if the graph has more than 4 vertices?

$\endgroup$
1
$\begingroup$

Because there is no path over 4 vertices, and the graph is connected, 1 'middle' vertice, to which all vertices are connected.

a-b

a-b-c

a-b-c-d <- this is wrong, it has a path over 4 vertices. so d has to be added adjacent to b instead.

in this way, b has to be connected to every vertices, for if it is not there would be a path over 4 vertices.

$\endgroup$
0
$\begingroup$

We are going apply induction on the number of vertices of $G$.

Statement:If $G$ is a connected simple graph with $n$ vertices and does not have $P_4$ or $C_4$ as an induced subgraph then $G$ has a vertex adjacent to all other vertices.

If $n=1,2,3$ then it is trivially true. Observe that for $n=3$ ; $G$ looks like: $P_3$ or $C_3$.

Suppose ,the given statment is true for all graph with vertices $\le(n-1)$ .

Let $v$ be a vertex of $G$ ,a connected simple graph with $n$ vertices and does not have $P_4$ or $C_4$ as an induced subgraph.Therefore $G-v$ is also connected simple graph with vertices $\le(n-1)$ and does not have $P_4$ or $C_4$ as an induced subgraph. So $G-v$ has a vertex(say $u$) adjacent to all other vertices and observe that $G-v$ have $P_3$ or $C_3$ as an induced subgraph.

Take $P_3$ as: $a-u-b$ and $C_3$ as:$a-u-b-a$(here a,b may not be unique). Now in $G$ if $v$ adjacent to only $u$ then the it complete the proof.If not say $v$ adjacent to only $a$ or $b$ ; then it contradicts to the fact that $G$ does not have $P_4$ as an induced subgraph. And if $v$ adjacent to any two of $\{a,u,b\}$ ; then it contradicts to the fact that $G$ does not have $C_4$ as an induced subgraph.

$\endgroup$
9
  • $\begingroup$ Your last sentence is not true... $\endgroup$ Sep 27 '13 at 8:26
  • $\begingroup$ It is still missing something : if $G-v$ is a complete graph, then there is no induced $P_3$ and thus if $v$ is adjacent only to $a$ you won't have a $P_4$. A shorter proof to finish yours: if $v$ is adjacent to $u$ or to a universal vertex it is fine. Else, $v$ is adjacent to a vertex, $a$, that has a non-neighbor $b$. Then $v-a-u-b$ is either an induced $P_4$ or and induced $C_4$. $\endgroup$ Sep 27 '13 at 11:56
  • $\begingroup$ So u think that: HERE $G-v$ may be complete graph ,with no vertices of $G>3$ ? $\endgroup$
    – jon
    Sep 27 '13 at 13:50
  • $\begingroup$ What does "with no vertices of G>3" mean ? $\endgroup$ Sep 27 '13 at 14:51
  • $\begingroup$ sorry, it is "number of vertices of G>3". $\endgroup$
    – jon
    Sep 27 '13 at 17:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.