Two graphs $G$ and $H$ are isomorphic if they have a function $f$ which provides an exact pairing of vertices in the two graphs such that for any adjacent vertices $u,v\in \{\mbox{set of vertices of }G\}$, $f(u)$ and $f(v)$ are also adjacent in $H$.

learn more… | top users | synonyms

1
vote
1answer
602 views

How can I tell how many non-isomorphic unrooted trees with 6 edges exists without drawing them all?

Typically my professor asks that we draw them all, but I would like to save some time to confirm how many I need.
2
votes
3answers
58 views

Nice Isomorphic Question and way of finding Quickly?

I see a question about Isomorphic Graph. the question is: The first line graph is not isomorphic with which one in the second line? How we can find isomorphic graph without knowing some geometry map ...
2
votes
1answer
27 views

Creating a Bijection to check if Graphs are Isomorphic

To prove that two graphs are isomorphic I was taught to first consider the bijection between the two graphs. I was never taught however the rules when coming up with the bijection. Is my only rule, ...
2
votes
0answers
13 views

are all transitive reductions of a graph isomorphic?

Transitive reduction of a graph is not unique. Take this example: Now if we remove the labels, the two reduced graphs are isomorphic: are all transitive reductions of a directed graph isomorphic ...
2
votes
0answers
31 views

Why is the graph of 4 nodes and 2 edges not self-complementary?

I am having some trouble seeing why a graph of 4 nodes and 2 edges is not self-complementary such that G is isomorphic to G bar (G complement) (please see the attachment below). I know that the number ...
1
vote
1answer
23 views

Reducing Subgraph Isomorphism Complexity via an Enforced Layout of Nodes

This is my first question on the mathematics stack exchange. I hope my question is at least a little interesting, then. In any case, I was reading up on the subgraph isomorphism problem on wikipedia. ...
2
votes
1answer
35 views

Adding an edge and a vertex to non-isomorphic graphs

Let $G$ and $H$ be two non-isomorphic simple graphs of equal order and equal size. Suppose I am to add a vertex $v$ and and edge $e$ incident to $v$ to $G$ and $H$. By add I mean to connect $v$ to ...
2
votes
1answer
35 views

What is a graph isomorphism?

I am trying to under isomorphism in graphs, and from what I know, if graph A is isomorphic to graph B, then you could basically just rearrange the nodes in A, while keeping the edges connected the ...
0
votes
0answers
23 views

Isomorphism testing for minimal SP-trees

I'm doing a bit of research on the SP-trees. I'm still new to this whole problematic, so I'd be thankful if someone cleared this thing up. :) This is the scenario that I'm trying to come up with a ...
-2
votes
3answers
80 views

Graph isomorphism when all vertices have the same degree

Are 2 connected graphs isomorphic if they have the same number of vertices and each vertex has the same degree $k$? I don't know how to prove it but I also can't find a counter example.
0
votes
1answer
68 views

How many nonisomorphic graphs are there with 10 vertices and 43 edges?

How would I go about solving this? I know that $K_{10}$ has $9+8+7+\dots+1=45$ edges. So would it be something like $\binom {45}{43}$ because out of the 45 total edges, one must choose 43 for the ...
20
votes
4answers
4k views

Are these 2 graphs isomorphic?

They meet the requirements of both having an $=$ number of vertices ($7$). They both have the same number of edges ($9$). They both have $3$ vertices of degree $2$ and $4$ of degree $3$. However, ...
3
votes
1answer
58 views

Isomorphisms of infinite graphs that are fixed on a set of vertices

Suppose we have two infinite directed graphs $\langle V,E\rangle$ and $\langle V,E^*\rangle$, and a set $A \subseteq V$ such that, for all finite $X \subseteq A$, there is an isomorphism from $\langle ...
1
vote
2answers
40 views
3
votes
1answer
3k views

How to draw all nonisomorphic trees with n vertices?

I have a textbook solution with little to no explanation (this is with n = 5): Could anyone explain how to "think" when solving this kind of a problem? (for example, drawing all non isomorphic ...
0
votes
0answers
71 views

Show that the number of isomorphism classes of tree on n vertices is exponentially large as a function on n.

I am currently trying to answer this question: 'Show that the number of isomorphism classes of tree on n vertices is at least $\frac{n^{n−2}}{n!}$ and hence that this is exponentially large as a ...
1
vote
1answer
204 views

Number of isomorphism classes of a tree on n vertices

I'm currently trying to solve this problem: "Show that the number of isomorphism classes of tree on n vertices is at least $\frac{n^{n-2}}{n!}$." I'm pretty stumped to be honest. I know of Cayley's ...
1
vote
1answer
40 views

Vertex degree and graph isomorphism

Suppose I have two simple graphs $G(V,E)$ and $H(V,E)$ with number of vertices $N$. And $\forall i \quad \text{such that}\quad 0<i<N$ No:of elements in $V(G)$ with degree $i $ = No:of elements ...
0
votes
2answers
40 views

Concept: The graph component

I have the following definition for a Component of a graph: A subgraph $H$ of a graph $G$ is a component of $G$ if $H$ is a maximal connected subgraph of $G$, ...
0
votes
1answer
49 views

Is the number of simple circuits of a particular length preserved in two isomorphic graphs?

If two graphs are isomorphic, and one has a simple circuit of a particular length, must the other graph also have a circuit of the same length? Do they also have to have the same number of such ...
0
votes
1answer
67 views

Any two abelian group of order 8 must be isomorphic

TRUE/FALSE :Any two abelian group of order 8 must be isomorphic SOLUTION: True The problem of finding all abelian groups of order 8 is impossible to solve, because there are infinitely many ...
5
votes
3answers
10k views

Prove two graphs are isomorphic

I have identified two ways of showing it isomorphic but since it is a 9 mark question I dont think i have enough and neither has our teacher explained or given us enough notes on how it can be ...
0
votes
1answer
59 views

Proving two graphs are isomorphic in polynomial time - Bondy/Murty - Graph Theory Page 6

I am trying to do the below problem: Now I can't see how one does this. I know you can explicitly show the bijections, but I can't see an easy way to do this, since it is $3\text{-regular}$. I ...
0
votes
1answer
53 views

Proof verification: (Pretty pictures :) )Showing two graphs are not isomorphic. Bondy/Murty - Graph theory Page 5

I want to show the below two graphs are not isomorphic. Treat the left as graph $\bf G$ and the right as graph $\bf H$. $\bf G$ and $\bf H$ are not isomorhpic: Although we have a bijective mapping ...
1
vote
2answers
94 views

How to calculate the number of automorphisms of a given graph?

How do determine the number of isomorphisms that a graph has to itself? For instance, suppose we have the following graph: How do I determine how many isomorphisms there are from G itself?
1
vote
1answer
47 views

$3$-connected graph isomorphism problem

If $G$ is $3$-connected, then $G$ contains a subgraph isomorphic to $H$, where $H$ is obtained from $K_4$ by replacing the edges of $K_4$ by internally disjoint paths. Any hints and proofs are ...
0
votes
1answer
32 views

How can I show complete graphs are determined by spectrum?

I understand how to prove a complete graph $K_n$ has spectrum $\lbrace -1^{(n-1)},n-1 \rbrace$. However I am having difficulty proving that the spectrum uniquely determines the complete graph. ...
1
vote
2answers
44 views

Are these graphs isomorphic?

Are these 2 graphs isomorphic? (sorry for the bad picture quality) For the solution: 1) They both have 8 vertices 2) They both have 12 edges 3) They both have 8 vertices of degree 3 4) Is this ...
1
vote
1answer
22 views

Nonisomorphic graphs Discrete Math

Find 3 different nonisomorphic graphs with 8 vertices that have the degree sequence 2,2,2,2,2,2,2,2. Answer: An 8-cycle, or two 4-cycles, or a 3-cycle and a 5-cycle. Can someone show me how these ...
1
vote
1answer
23 views

isomorphism of graph

I have a doubt about an example of isomorphism of graphs. I am looking at the notes of group theory by Donald Kreher. (http://www.math.mtu.edu/~kreher/ABOUTME/syllabus/GTN.pdf). Please see page 9 ...
1
vote
2answers
95 views

Isomorphism vs equality of graphs

I have just started studying graph theory and having trouble with understanding the difference b/w isomorphism and equality of two graphs.According what I have studied so far, I am able to conclude ...
1
vote
0answers
32 views

How many different graphs are there with a given degree-sequence?

Let G be a simple undirected graph. If it has at most $4$ edges, there is only one graph for any degree-sequence, but for $n = 5$, the situation changes. There are $34$ different (non-isomorphic) ...
0
votes
1answer
35 views

A graph with minimum degree $k+2$ contains any $(k+3)$-vertex tree as a subgraph?

Let $k$ be a positive integer and let $T$ be a tree of order $k+3$. If $G$ is a graph with minimum degree at least $k+2$, prove that $G$ contains a subgraph isomorphic to $T$. Any solutions or hints ...
0
votes
1answer
113 views

Calculating the number of isomorphic classes of complete bipartite graph

How many isomorphism classes of complete bipartite graphs have exactly 10 vertices? I don't understand what the question is asking or how to go about solving it.
0
votes
1answer
57 views

Graph isomorphism problem for labeled graphs

In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is ...
1
vote
1answer
60 views

Finding all mapping between two isomorphic graphs

Is there any formula for counting all the mappings between two isomorphic graphs? I have the following two graphs. and I am trying to find the mappings in the following way. For each edge in ...
2
votes
0answers
36 views

Splitting a graph into two isomorphic parts

Say a graph $G$ has $2n$ vertices. I'd like to know if I can partition the vertices of $G$ into two parts $X$ and $Y$ such that $G[X]$ is isomorphic to $G[Y]$ ($G[S]$ denotes the subgraph of $G$ ...
1
vote
1answer
48 views

Promises in the hidden subgroup formulation of graph isomorphism problem

In the 3rd slide of the talk, Graph isomorphism, the hidden subgroup problem and identifying quantum states, by Pranab Sen, the promise of the problem is defined as follows. Given: $G$: group, ...
3
votes
1answer
36 views

Confusion about the hidden subgroup formulation of graph isomorphism

I am going through Quantum factoring, discrete logarithms and the hidden subgroup problem by Richard Jozsa. On page 13, the author discussed the hidden subgroup problem (HSP) formulation of the graph ...
1
vote
1answer
97 views

Cayley's theorem : precision

I have the form of Cayley's theorem that doesn't say any more than : for every finite group G there exists n such that Sn has a subgroup which is isomorphic to G. Now I'd be interested in knowing ...
0
votes
2answers
252 views

What's the difference between the automorphism and isomorphism of graph?

What's the difference between the automorphism and isomorphism of graph? In graph theory, an isomorphism of graphs $G$ and $H$ is a bijection between the vertex sets of $G$ and $H$, $ f \colon ...
1
vote
1answer
26 views

Graph Isomorphism with Same Degree Sequece

How do I prove that two tree graphs with the same degree sequence are isomorphic (or non isomorphic)? Thanks for the help!
0
votes
1answer
33 views

Show isomorphy by mapping generators onto generators only

If I want to show that two cyclic groups are isomorphic, is it enough to show that their cardinality is the same and that the generators of the groups are mapped onto each other? To be precise: I am ...
0
votes
1answer
50 views

only trivial automorphism on Frucht graph

Why is there only the trivial automorphism on the Frucht graph? We have a rooted tree in the Frucht graph which allows to totally order the vertices. But how does this imply that there is only the ...
1
vote
3answers
61 views

Isomorphisms and Automorphisms

An automorphism is a mapping of a graphs nodes onto it's own nodes. Whereas an isomorphism is the mapping of a graphs nodes onto another graphs nodes. Doesn't this mean the are fundamentally the ...
2
votes
2answers
37 views

Construct Pairs of Non Isomorphic Graphs

I Have the following question : Give three examples of simple, connected graphs, all with 8 vertices with degrees 2, 2, 2, 2, 3, 3, 4 and 4, no pairs of which are isomorphic What is the best ...
1
vote
1answer
319 views

How to determine number of isomorphic classes of simple graph with n vertices, each with degree m?

For HW, I need to find the number of isomorphic classes of a simple graph with 7 vertices, each with degree two. I know I could brute-force it by finding all edge sets that fulfill that criteria, but ...
-1
votes
1answer
353 views

Given three non-isomorphic spanning trees of the complete graph K5, how many trees in each class?

The graph, K5 has 125 different spanning trees, which I beleive fit into three different non-isomorphic classes of spanning trees. However, I'm at odds as to how to figure out how many are in each ...
0
votes
3answers
81 views

Show that the polynomial ring in $n-1$ variables is isomorphic to the polynomial ring in one variable $x_{n}$

For a ring $R$ and for $n \geq 1$, define $ S := R[x_{1},...,x_{n-1}]$ for the polynomial ring in $n-1$ variables with coefficients in $R$. Show that $R[x_{1},...,x_{n}]$ is isomorphic to the ...