Graph Theory - How do I construct this graph?

In summary, the conversation discusses a problem that can be solved using graph theory. The problem involves showing that there must be a set of at least three people who are friends or a set of at least three people who are complete strangers in a group of six people. The speaker asks for help in constructing a graph with six nodes and asks questions about the number of edges, whether a directed graph is necessary, and where to place the edges. It is suggested to look for a coloring problem in a graph theory or combinatorics text, and use a "step by step" proof approach.
  • #1
arunma
927
4
Graph Theory -- How do I construct this graph?

I have a question which I think I'm supposed to solve using graph theory. Here's the problem statement:

"Given 6 people, suppose that the relationship between them is that they are either friends or complete strangers. Show that there must be a set of at least three people who are friends or a set of at least three people who are complete strangers."

Now this isn't specifically a graph theory course, but I'm guessing that I have to construct a graph with six nodes. A few questions: how many edges should the graph have? Is it necessary to use a directed graph? And where should I place the edges with respect to the nodes? I'm fairly certain that if I can construct the right graph, the problem will become almost trivial.

Anyway, I'd really appreciate some help with this if anybody is able. I've been thinking about this problem for some time now, and it's starting to drive me crazy. Thanks in advance.
 
Physics news on Phys.org
  • #2
its a Coloring problem with a "step by step" proof. There are many similar problems. Look in a graph theory text or combinatorics text for the term colouring/coloring or the like. There's a specific chapter on this from my old text, by bondy. The only hint i should need to give you is use "color(s)"
 
  • #3
I have not done a problem like this before, but going by what Neurocomp says you can do a "step by step" proof if you start in the right place. The first thing to realize that a given node has five edges--so that the node either has at least three "friend" edges or at least three "stranger" edges. Step by step from there is not hard.
 

1. What is a graph and what are its components?

A graph is a mathematical structure used to represent relationships between objects. It is composed of vertices, which represent the objects, and edges, which represent the connections between the objects.

2. How do I represent a graph visually?

A graph can be represented using a diagram, where the vertices are represented by circles or points, and the edges are represented by lines connecting the vertices.

3. How do I construct a graph from a real-world problem?

To construct a graph, start by identifying the objects or entities in the problem and representing them as vertices. Then, determine the relationships between the objects and represent them as edges.

4. What are the different types of graphs and when should I use each one?

The two main types of graphs are directed and undirected. A directed graph has edges with a specific direction, while an undirected graph has edges without a specific direction. Directed graphs are useful for representing relationships with a specific direction, while undirected graphs are useful for representing symmetric relationships.

5. Are there any algorithms or techniques for constructing graphs?

Yes, there are various algorithms and techniques for constructing graphs, such as depth-first search, breadth-first search, and Dijkstra's algorithm. These algorithms can help to find the shortest path between two vertices, determine the connectivity of the graph, and more.

Similar threads

Replies
1
Views
757
  • General Math
Replies
5
Views
984
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Programming and Computer Science
Replies
8
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Calculus and Beyond Homework Help
Replies
14
Views
1K
  • Introductory Physics Homework Help
Replies
10
Views
617
  • Programming and Computer Science
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
32
Views
2K
Replies
2
Views
671
Back
Top