Welcome to our community

Be a part of something great, join today!

Problem on Graph Theory and Algorithms

iany00

New member
Nov 4, 2012
1
G = (V, E) a graph with V = {1, . . . , n}. We have the function f : V → V defined
f (v) = min{u|u ∈ V, dG (v, u) ≤ 2}.


Demostrate that vw ∈ E(G) with f (v) != f (w) then G has the
P4 subgraph induced

I don;t understand what to demostrate/to do. Any advice?
 

Sudharaka

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
G = (V, E) a graph with V = {1, . . . , n}. We have the function f : V → V defined
f (v) = min{u|u ∈ V, dG (v, u) ≤ 2}.


Demostrate that vw ∈ E(G) with f (v) != f (w) then G has the
P4 subgraph induced

I don;t understand what to demostrate/to do. Any advice?
Hi iany00, :)

I don't know the answer to your question, but the exact same question (although differently worded), is asked at Stack Exchange.

graph theory - Prove that if $G$ is P4-free then any two vertices $u$ and $v$ are in the same connected component if and only if $f(u) = f(v)$ - Mathematics

Hope this helps.

Kind Regards,
Sudharaka.