What is the Definition of a Component in a Graph?

  • Context: Undergrad 
  • Thread starter Thread starter e(ho0n3
  • Start date Start date
  • Tags Tags
    Components Graph
Click For Summary

Discussion Overview

The discussion revolves around the definition of a component in graph theory, specifically addressing the nature of connected subgraphs and the concept of maximality. Participants explore the implications of these definitions through specific problems and examples, seeking clarity on the distinctions between connected subgraphs and components.

Discussion Character

  • Conceptual clarification
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant suggests that a component of a graph G is simply a connected subgraph of G, expressing doubt about the definitions encountered.
  • Another participant clarifies that a component is defined as a maximal connected subgraph, meaning it cannot be contained within any larger connected subgraph.
  • Concerns are raised regarding the requirement that each edge in a subgraph must have both vertices present in that subgraph, with examples provided to illustrate potential misunderstandings.
  • Discussion includes the notion of minimal connected subgraphs, with participants attempting to define what constitutes minimality in this context.
  • One participant shares an example to illustrate the concept of maximal connectedness, emphasizing that a maximal subgraph contains as many edges and vertices as possible while remaining connected.
  • Another participant acknowledges a misunderstanding regarding the nature of subgraphs, particularly in relation to the inclusion of edges based on vertex presence in the supergraph.

Areas of Agreement / Disagreement

Participants express differing views on the definition of a component, particularly regarding the necessity of maximality. While some agree on the importance of connectedness and maximality, others remain uncertain about the implications of these definitions.

Contextual Notes

Participants highlight potential ambiguities in the definitions of subgraphs and components, particularly concerning the inclusion of edges and the conditions under which a subgraph is considered maximal or minimal.

Who May Find This Useful

This discussion may be useful for students and practitioners in mathematics and computer science, particularly those studying graph theory and its foundational concepts.

e(ho0n3
Messages
1,349
Reaction score
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
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.
 
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.
 
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:
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:
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.
 

Similar threads

Undergrad Question regarding degrees of a graph and its biconnected components
  • · Replies 34 ·
2
Replies
34
Views
7K
Graduate Interesting graph theory problem
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Finding the chromatic number of a graph with biconnected components
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Why is Graham's number a factor of 3?
  • · Replies 12 ·
Replies
12
Views
5K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
4K
Graduate What are K6 and the multidesign problem in graph theory?
  • · Replies 1 ·
Replies
1
Views
2K
Strong Induction, Tangled Graph
  • · Replies 3 ·
Replies
3
Views
3K
Undergrad Edge connectivity of a graph given the number of edge disjoint paths
  • · Replies 1 ·
Replies
1
Views
2K
Is Partitioning a Graph into Two Sets a Cut Set?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Graphs with N Nodes: Proving Cliques and Anti-Cliques
  • · Replies 6 ·
Replies
6
Views
3K