MHB Problem on Graph Theory and Algorithms

AI Thread Summary
The discussion revolves around a problem in graph theory involving a function f defined on the vertices of a graph G. The task is to demonstrate that if two vertices v and w are connected (vw ∈ E(G)) and f(v) is not equal to f(w), then G must contain a P4 subgraph. Participants express confusion about the demonstration requirements and seek clarification. A suggestion is made to refer to a similar question on Stack Exchange for further insights. Understanding the relationship between the function f and the structure of the graph is crucial for solving the problem.
iany00
Messages
1
Reaction score
0
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?
 
Physics news on Phys.org
iany00 said:
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.
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...

Similar threads

Replies
22
Views
2K
Replies
1
Views
2K
Replies
2
Views
1K
Replies
6
Views
2K
Replies
2
Views
3K
Replies
8
Views
2K
Back
Top