Can the number of edges determine isomorphism in graphs?

  • Thread starter Thread starter AlbertEinstein
  • Start date Start date
  • Tags Tags
    Graphs Isomorphism
AI Thread Summary
The discussion centers on whether having the same number of edges is sufficient to prove that a graph G and its complement G' are isomorphic. It is clarified that this is not enough, as demonstrated by examples of graphs with four vertices and three edges that do not have isomorphic complements. To establish isomorphism, one must define a function that maps vertices of G to G' while preserving edge connections. The initial inquiry reflects a common misconception about graph isomorphism. Understanding the requirements for proving isomorphism is crucial in graph theory.
AlbertEinstein
Messages
113
Reaction score
1
Hi all,

If I have to prove that the graph G and its complement G' are isomorphic, then is it enough to prove that both G and G' will have the same number of edges. Intuitively its clear to me, but how do I prove this. If there's a counterexample, please post.

Thanks in advance.
 
Mathematics news on Phys.org
AlbertEinstein said:
Hi all,

If I have to prove that the graph G and its complement G' are isomorphic, then is it enough to prove that both G and G' will have the same number of edges. Intuitively its clear to me, but how do I prove this. If there's a counterexample, please post.

Thanks in advance.

That is certainly not enough. Consider the graphs of four vertices and three edges. They are not isomorphic to each of their complements.
To prove an isomorphism you will need to define a function f : G --> G' such that an edge between v_1 and v_2 implies that there is an edge between f(v_1) and f(v_2).
 
Oh yeah, I got the point.

Thanks for the help.
 

Thread 'Non-orthogonal bases'

Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
View full post »

Thread 'What Exactly is Dirac’s Delta Function? - Insight'

Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...
View full post »

Similar threads

I Classify the isomorphism of a graph
Replies
3
Views
2K
I Finding if a subgraph of a minimal non-planar graph is maximal planar
Replies
1
Views
1K
I Find Smallest Subtree of G w/ Nodes from S
Replies
5
Views
2K
I The number of intersection graphs of ##n## convex sets in the plane
Replies
2
Views
1K
I Prove that a given graph contains a cycle using induction (Graph Theory)
Replies
7
Views
3K
I Edge connectivity of a graph given the number of edge disjoint paths
Replies
1
Views
1K
I Can chatgpt accurately calculate expected lengths in Pascal's triangle?
2
Replies
66
Views
6K
B 4-colours theorem can be proved visually
Replies
21
Views
2K
How to prove that 2 graphs are not isomorphic?
Replies
4
Views
11K
B Proving the area formula for a rectangle for all positive real numbers
Replies
10
Views
2K

Hot Threads

Recent Insights

Back
Top