Defining a component as a maximally connected subgraph, is there a way to prove (or a counter-example) that every vertex belongs to some component, even in the case of infinite graphs? I know you can just build the components for finite graphs, but how would you ensure maximality in the infinite case?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
0
|
||||||
|
closed as off topic by Andreas Blass, Andreas Thom, Stefan Geschke, Timothy Chow, Qiaochu Yuan Jul 18 2011 at 17:03 |
|
0
|
You just define an equivalence relation on the vertices: Two vertices are equivalent if they are connected by a (finite) path. It is easily checked that this is an equivalence relation. The equivalence classes are the components of the graph, no matter whether the graph is finite or infinite. Maximality of each equivalence class (as a connected set) should be clear. It is important to notice that while there are infinite paths, take for example the graph on the integers where any two successive numbers are connected by an edge, these infinite paths cannot have two endpoints. Hence it makes not sense to talk about infinite paths in the definition of a component. |
|||
|
|
