Graph Theory Proof: Number of Vertices and Edges in a Connected Graph

In summary: I'm sorry that was not helpful.In summary, the number of vertices and edges in a graph is determined by the cut induced by every proper nonempty subset of vertices.
  • #1
beddytear
5
0

Homework Statement



Let G be a graph with at least two vertices, such that the cut induced by every
proper nonempty subset of vertices of G contains exactly two elements. Determine
(with proof ) the number of vertices and edges in G.

Homework Equations



Connectedness. A graph G is connected if for any two vertices x and y in G, there is a path from x to y.

The Attempt at a Solution


I'm really stuck. But i think proving by contradiction is a good approach (maybe??).
i.e.: Suppose the graph is not connected...i.e. it has more than one component. ...?
this is a contradiction...therefore the graph is connected?
like i said. I'm really having troubles. any help would be greatly appreciated.
thanks in advance.
 
Physics news on Phys.org
  • #2
What do you mean by the cut induced...? I don't remember hearing that specific usage of the word cut regarding graph theory but I may have just forgotten
 
  • #3
Given a subset X of the vertices of G, the cut induced by X is the set of edges that have exactly one end in X.

Maybe the theorem: A graph G is not connected if and only if there exists a proper nonempty subset X of V(G) such that the cut induced by X is empty helps?
 
  • #4
Ok, so you're given a graph G. For any subset of G, say X, there are exactly two edges going from X to G-X

Start by picking a single vertex in G and notice that if X is a single vertex, that vertex has to have degree 2. What are your possible choices for G? Then by picking other subsets X narrow it down further
 
  • #5
still lost. if i pick 2 vertices...? 3 vertices?
 
  • #6
It will help if you write down exactly what the set of all possible connected graphs are for which every vertex has degree 2
 

FAQ: Graph Theory Proof: Number of Vertices and Edges in a Connected Graph

How do I prove that a graph is connected?

To prove that a graph is connected, you can use the method of induction. Start by selecting any two vertices and finding a path between them. Then, assume that the graph is connected for n vertices and add one more vertex. If this new vertex is connected to any of the existing n vertices, then the graph remains connected. Continue this process until you have proven that all vertices are connected.

What is the difference between a tree and a graph?

A tree is a special type of graph that does not contain any cycles. This means that there is only one path between any two vertices. In contrast, a graph can have multiple paths between vertices and can contain cycles.

How do I prove that a graph is a bipartite graph?

To prove that a graph is bipartite, you need to show that all of its vertices can be divided into two distinct sets such that there are no edges between vertices within the same set. This can be done by using the concept of colorings, where one set of vertices is assigned one color and the other set is assigned a different color. If there are no edges between vertices of the same color, then the graph is bipartite.

What is the difference between a directed graph and an undirected graph?

A directed graph is a graph where the edges have a specific direction, meaning that they can only be traversed in one direction. This is represented by arrows on the edges. In contrast, an undirected graph has edges that can be traversed in both directions, meaning there are no arrows on the edges.

How do I prove that a graph is planar?

To prove that a graph is planar, you can use Euler's formula, which states that for a connected planar graph with n vertices, m edges, and r regions, n - m + r = 2. If you can rearrange this equation to show that the number of regions is less than or equal to 2, then the graph is planar. Additionally, you can use the Kuratowski's theorem to check for the presence of a subdivision of K5 or K3,3 within the graph, which would make it non-planar.

Similar threads

Prove the decomposition of a graph w/ even edges produce a 2-path set
Replies
1
Views
1K
Domination number of a graph G
Replies
9
Views
1K
Strong Induction, Tangled Graph
Replies
3
Views
3K
How to construct a graph with girth = twice the diameter + 1
Replies
2
Views
2K
Prove that there exists a graph with these points such that....
Replies
2
Views
1K
Proving Cut Vertices in Simple Graphs
Replies
2
Views
1K
Can a Connected Graph with 2k Odd Vertices be Composed into k Trails?
Replies
11
Views
4K
Proving a (known isomorphic) graph is isomorphic
Replies
6
Views
2K
Proving uniqueness of almost irregular graphs with equal degrees for n=2k
Replies
3
Views
2K
Graph Theory: Finding the number of vertices
Replies
5
Views
13K

Hot Threads

Recent Insights

Back
Top