What is the Definition of a Component in a Graph?

[e(ho0n3]

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...

 

[TenaliRaman]

http://mathworld.wolfram.com/ComponentGraph.html

 

[HallsofIvy]

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.

 

[e(ho0n3]

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?

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.

 

[TenaliRaman]

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

 

[grady]

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.

 

[e(ho0n3]

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.