What is the Definition of a Component in a Graph?

In summary, a component of a graph G is a maximal connected subgraph, meaning it is not properly contained in any other connected subset. This means that a component is not simply a connected subgraph, but the largest possible subset that is still connected. It is important to require that each edge in a subgraph have both vertices in that subgraph, as this ensures that the subgraphs are indeed components. A minimal connected subgraph would be the smallest subset that is still connected. This concept is similar to other "maximal" concepts, such as a maximal path.
  • #1
e(ho0n3
1,357
0
Two questions:

Show that if G' is a connected subgraph of a graph G, then G' is contained in a component.

Show that if a graph G is partitioned into connected subgraphs so that each edge and each vertex in G belong to one of the subgraphs, the subgraphs are components.

Basically the problem is my shady notion of what a component is. I've read a couple of definitions, but I'm still dubious. From what I understand, a component of a graph G is nothing more than a connected subgraph of G. If this is true, then the aforementioned problems are trivially trivial. Hmm...
 
Mathematics news on Phys.org
  • #3
No, that's not the definition of "component". A component is not just a connected subgraph but a maximal connected subgraph: it is not properly contained in any connected subset. Of course, the first problem is still "trivial": it follows directly from that definition.

As far as the second is concerned, it is crucial that you require that each edge in a subgraph have both vertices in that subgraph.

For example, if your graph has 3 vertices, {A, B, C} and 2 edges a (connecting A,B) and b (connecting {B,C}), if you allow a subgraph to have the single vertex {A} and single edge a, the statement would not be true.
 
  • #4
The word "maximal" seems to be the culprit of my misunderstanding. Say G' is a maximal connected subgraph of the connected graph G. Then G' = G? And what would be a minimal connected subgraph?

HallsofIvy said:
As far as the second is concerned, it is crucial that you require that each edge in a subgraph have both vertices in that subgraph.
Required!? Isn't that implied by the fact that we have a subgraph. Is it possible to have a subgraph whose vertex set is null (i.e. only edges)? Maybe my notion of a subgraph is to blame for my misunderstanding.

By the way, the mathworld definition didn't help.
 
  • #5
Quote:
The word "maximal" seems to be the culprit of my misunderstanding

and why??
the largest subset G' of G=(V,E) such that G' is connected gives u a maximal subgraph.

This answers ur first question.

Quote:
And what would be a minimal connected subgraph?

simple the smallest subset G' of G=(V,E) such that G' is connected is the minimal connected subgraph.

-- AI
 
Last edited:
  • #6
e(ho0n3 said:
The word "maximal" seems to be the culprit of my misunderstanding.

To be more explicit, maximal with respect to connectedness. In other words a maximal connected subgraph is connected and contains as many edges and vertices as possible.

http://members.cox.net/gradyfield/graph.png

In the picture, the subgraph with Vertices={A,B,C,D} and Edges={(A,B),(B,C),(C,D)} is not maximal with respect to connectedness because you can add (A,D) to Edges and the graph will still be connected. After you add (A,D) though, you can not add anymore edges or vertices and stay connected. So the subgraph with (A,D) added is maximal with respect to connectedness, and it is a component.

There are other examples of maximal such and such. For example the concept of a maximal path is useful for proving a few things. A maximal path is a path such that no more edges can be added to the path without revisiting a vertex.
 
Last edited by a moderator:
  • #7
I see now. I was misunderstanding the concept of a subgraph. I always thought that if v and w were vertices in a subgraph and (v,w) existed in the supergraph, the (v,w) is also existed in the subgraph.

Thank you for clearing that up.
 

Related to What is the Definition of a Component in a Graph?

1. What are the main components of a graph?

The main components of a graph are the x-axis, y-axis, data points, and labels. The x-axis represents the independent variable, while the y-axis represents the dependent variable. Data points are plotted on the graph to show the relationship between the two variables, and labels are used to identify the variables and their units of measurement.

2. What is the purpose of the x-axis and y-axis in a graph?

The x-axis and y-axis serve as the reference lines on a graph. They help to establish the scale and orientation of the graph and allow for accurate interpretation of the data points. The x-axis typically represents the input or independent variable, while the y-axis represents the output or dependent variable.

3. How are data points represented on a graph?

Data points are usually represented by a symbol, such as a dot or a cross, on a graph. The position of the symbol on the graph corresponds to the values of the independent and dependent variables. Multiple data points can be plotted on a graph to show the relationship between the variables.

4. What is the importance of labels on a graph?

Labels are important on a graph because they provide information about the variables being plotted and their units of measurement. They help to clarify the meaning of the data and make the graph easier to understand. Labels also allow for accurate interpretation and comparison of data points.

5. How can the components of a graph be manipulated to change the representation of the data?

The components of a graph can be manipulated in various ways to change the representation of the data. For example, changing the scale of the x-axis or y-axis can make the data appear more spread out or condensed. Adding or removing labels can also change the interpretation of the data. Additionally, different types of graphs, such as bar graphs or pie charts, can be used to represent the same data in different ways.

Similar threads

I Question regarding degrees of a graph and its biconnected components
    • General Math
Replies
34
Views
4K
Interesting graph theory problem
    • General Math
Replies
1
Views
1K
I Finding the chromatic number of a graph with biconnected components
    • General Math
Replies
1
Views
1K
I Why is Graham's number a factor of 3?
    • General Math
Replies
12
Views
3K
I Prove that a given graph contains a cycle using induction (Graph Theory)
    • General Math
Replies
7
Views
2K
MHB Chordal graphs and perfect elimination orderings
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
Strong Induction, Tangled Graph
    • Calculus and Beyond Homework Help
Replies
3
Views
2K
I Question about a definition in Rivasseau's book
    • High Energy, Nuclear, Particle Physics
Replies
1
Views
1K
MHB Is Partitioning a Graph into Two Sets a Cut Set?
    • Math POTW for University Students
Replies
1
Views
1K
MHB Graphs with N Nodes: Proving Cliques and Anti-Cliques
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K

Hot Threads

Recent Insights

Back
Top