Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

-1
votes
3answers
398 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 ...
0
votes
0answers
27 views

Proof for maximum number of leaves in a tree with a given hopping distance

Hi I need help to prove the following for tree graphs which I believe is true: A tree with hopping distance $k$ (i.e. the most number of edges that any two vertices are apart) and n leaves either has ...
1
vote
1answer
69 views

Finding Automorphisms of Irregular graph through Regular Sub-Graphs.

Objective : To find a set of permutations for a irregular graph which is also a set of automorphism. This finding process uses permutations of 2 regular subgraphs of the given graph. Description and ...
0
votes
2answers
73 views

Limit of an absorbing random walk. (Limit of power of real symmetric matrix)

I have a problem that comes from absorbing random walks on a connected undirected graph $G$ with two types of nodes, absorbing nodes and free nodes. We randomly pick a node to start, once the random ...
1
vote
1answer
21 views

Problem in understanding a notation in graph theory (intersection of edges)

On the French wikipedia, one can read: Soit un graphe simple non orienté $G = ( S, A )$ (où $S$ est l'ensemble des sommets et $A$ l'ensemble des arêtes, qui sont certaines paires de sommets), un ...
3
votes
1answer
32 views

Diameter of Schreier coset graphs.

I'm looking for a source from which to learn about Schreier coset graphs. Especially, examples in which combinatorial properties (specifically, diameter) of Schreier graphs are calculated. Also, is ...
7
votes
2answers
202 views

Average degree in graph

Let $G=(V,E)$ on at least k+1 vertices Assume for every $u\neq v \in V$ s.t. $(u,v) \notin E$ we have $deg(u)+dev(v) \geq 2k$ . Prove that the average degree is at least $k$. I tried ...
2
votes
0answers
76 views

Help to write a proof (category theory diagram)

It is known that $f$, $g$, $h$ are isomorphisms. It is known that $g\circ f = h^{-1}$. I need to write down the proof of the following theorem. I am an amateur mathematician and am not an expert in ...
0
votes
1answer
35 views

Is it possible for a graph to have an Euler circuit and an Euler path?

Is it true that an Euler path should have two vertices of odd degree and an Euler circuit should have no vertices of odd degree? Is it therefore impossible to have a graph with both an Euler path and ...
1
vote
1answer
35 views

In a bipartite graph $\alpha \beta \geq m$

That's basically it. $\alpha$ is the cardinality of the biggest independent set (no pair of vertices is connected) and $\beta$ is the cardinality of the smallest covering by vertices. I know this ...
0
votes
2answers
46 views

Argument for the diameter of these 2 graphs…

I believe G1 has a diameter of 2 & G2 has a diameter of 4. However, is there a formal way to prove / argue for these given diameters? I'd like to see an argument without having to list all the ...
3
votes
1answer
126 views

Construction of a Strongly Regular Graph which has regular Neighbourhood graphs in all iteration.

Notation and Definition: $G$ is a Strongly Regular Graph (not complete or a cycle) and is denoted by $\mathrm{SRG}(n,r, \lambda, \mu)$ if it has the following properties: Every two adjacent ...
1
vote
1answer
297 views

Finding all spanning trees of a strongly connected directed graph

I have a strongly connected directed graph with about 10 vertices and 20 edges, and would like to find all spanning trees anchored at each vertex. Is there a systematic way, or a tested ...
6
votes
2answers
3k views

Show that there's a minimum spanning tree if all edges have different costs

Show that there's a unique minimum spanning tree (MST) in case the edges' weights are pairwise different $(w(e)\neq w(f) \text{ for } e\neq f)$. I thought that the proof can be done for example ...
2
votes
1answer
395 views

Transitive tournament

1.) Prove that an orientation of $K_n$ is a transitive tournament if and only if it does not have any directed cycles of length $3$. 2.) Prove that a tournament is strongly connected if and only if ...
1
vote
0answers
53 views

Notation about commutative diagrams and their vertices

Usually vertices of a commutative diagram are labeled with objects like $A\overset{f}{\leftrightarrow} B$. But now I want to distinguish between vertices of the diagram even if they happen to ...
0
votes
0answers
19 views

For graphs in a recursive graph class: Does m = O(n) hold?

For recursive k-terminal Graph classes - for example definied in this paper - is it true that |E| = O(|V|)? If so, I would be very grateful for a reference! Thanks!
3
votes
1answer
28 views

Prove that, for all $v\in\left(\mathbb E^3\right)^n$, $\langle Lv,v\rangle=\frac{1}{2}\sum_{i,j}^n a_{ij} \|v_i-v_j\|^2.$

Given a nonnegative, symmetric, $n\times n$ matrix $A$ the Laplacian $L$ of $A$ is defined to be $L=D-A$, where $D=\operatorname{diag}(d_1,\dots,d_n)$ and $d_l=\sum_{j=1}^n a_{lj}$. The Laplacian as ...
1
vote
1answer
43 views

Maximizing colored vertices of a graph $G$ having less than $\chi(G)$ colors

Consider a $k$-partite graph $G$ of $N$ nodes and $q$ different colors with $q < k = \chi(G)$. I would like to determine how many vertices can I color at most with these $q$ colors. Consider the ...
4
votes
1answer
367 views

Fastest way to try all passwords

Suppose you have a computer with a password of length $k$ in an alphabet of $n$ letters. You can write an arbitrarly long word and the computer will try all the subwords of $k$ consecutive letters. ...
3
votes
2answers
232 views

Number of self-avoiding rook walks in a rectangular grid

I was wondering how many self-avoiding rook walks there are on an $m×n$ grid. A self-avoiding rook walk is a path from the bottom left corner to the top right corner of the grid, composed only of ...
1
vote
1answer
54 views

Max flow on undirected graph with constrained edges

I've been trying for a while to develop an algorithm that counts the maximum number of disjoint vertex paths in a graph, but with an addition of "forced paths". Forced paths are here marked with bold ...
8
votes
2answers
105 views

Vertex Reconstruction Conjecture For Asymmetric Graphs

Simple question: (a) Is it known whether all graphs G having trivial aut(G) are vertex reconstructible, and (b) what is the proof if it exists?
1
vote
0answers
67 views

How do we prove commutativity of a diagram?

How do we prove commutativity of a diagram? There may be an infinite number of paths. We can't enumerate all paths.
5
votes
2answers
100 views

Automorphism groups of vertex transitive graphs

Does there exist a finite nonoriented graph whose automorphism group is transitive but not generously transitive (that is, it is not true that each pair $(x,y)$ of vertices can be interchanged by some ...
0
votes
1answer
35 views

Every cycle is a composition of simple cycles

In a directed multigraph: Every cycle (closed walk) is a composition of simple cycles, right? Moreover, every finite path is a composition of simple paths, right? What is the simplest proof of ...
4
votes
0answers
29 views

Lower bound for spectral gap for graph on $n$ vertices

Let $G = (V,E)$ be a graph on the vertex set $V$ with edges $E$. Let $A$ be the adjacency matrix for $G$ (so $A_{ij} = 1$ if vertices $v_i$ and $v_j$ are connected by an edge), and $D$ be the ...
1
vote
0answers
29 views

Adjacency matrix of a square of a graph.

What is the relation between $A(G)$ and $A(G^2)$? Where $G^2$ is the square of a graph $G$ and $A(G^2),A(G)$ their respective adjacency matrix.
2
votes
1answer
55 views

How do I determine the domain and range of the following relations using set builder notation?

I have been given the following relations to find the domain and range of using builder notation. (The blue writing is what I have so far) I am just beginning to learn the whole concept of set ...
0
votes
2answers
421 views

Cycle containing two given nodes in an undirected graph

Given an undirected graph G=(V,E) and two nodes s, t in V, how to FIND an arbitrary SIMPLE cycle (each node used only once) between s and t? Or just DETECT whether there is a cycle between them? Here ...
0
votes
0answers
11 views

Smallest near triangulation of the plane with an external face of size $4$ for which all interior vertices have minimum degree $5$?

Consider the near-triangulation $G$ with an external face of size $4$. What is the minimum number of interior vertices for which G has minimum degree 5 as to those vertices? The degrees of the $4$ ...
0
votes
0answers
24 views

Graph Laplacians - self-study

I am self-studying graph laplacians in Kevin Murphy’s book “A probabilistic perspective on machine learning”. I understand that we introduce the vector f to proof that the matrix is positive ...
2
votes
1answer
40 views

Graph Theory - Bipartite Matchings

Under what conditions can the symmetric difference between a (non-maximal) matching $M$ and a maximal matching $M*$ contain a path of length $\geq 2$? The problem is to show that every vertex in the ...
1
vote
0answers
23 views

factor graphs - example

I am self-studying graphs - and stumbled upon factor graphs - e.g. as described on https://en.wikipedia.org/wiki/Factor_graph. I have trouble concretizing what the factor vertices represent. Would ...
1
vote
1answer
42 views

Longest path technique of proving a graph theory problem

Question: Let G be a simple graph, where the minimum degree of a vertex is k. Show that G contains a path of length at least k and a cycle of length at least k + 1. Proof: Consider the longest ...
1
vote
1answer
61 views

Number of Automorphisms of a Irregular Graph.

I have been looking for results on number of graph automorphisms of irregular graph(upper and lower bound). I searched , but could not find anything which can be used directly. Say, $G$ is $k$ ...
12
votes
3answers
146 views

Game on simple finite graphs

Consider the following game on graphs (no multiple edges, but graphs can be disconnected). Players A and B alternate picking a vertex. After picking a vertex, a number is assigned to that vertex such ...
19
votes
11answers
9k views

Graph theory software?

Is there any software that for drawing graphs (edges and nodes) that gives detailed maths data such as degree of each node, density of the graph and that can help with shortest path problem and with ...
2
votes
2answers
136 views

Union of two matching sets being a matching

Let $G$ be a bipartite graph with parts $A$ and $B$. Let $U\subseteq A$ and $V\subseteq B$ and assume that there exists matching in $G$ that covers all vertices in $U$ and another matching that covers ...
1
vote
1answer
71 views

Extending matchings in a bipartite graph

Could I get some help for part b(i) of below please? Thanks. (Part (a) follows from Hall's Marriage Thm, and b(ii) follows quickly from b(i) I think). Let $G$ be a bipartite graph with parts $X$ and ...
1
vote
0answers
35 views

A question regarding matchings in bipartite graphs

Let $G=(V,E)$ be a graph with $V(G)=X\cup Y$, let $M_1$ be a matching that "covers" $X'\subseteq X$, and let $M_2$ be a matching that "covers" $Y'\subseteq Y$. Show that then there is a matching $M$ ...
1
vote
2answers
56 views

Given $G = (V,E)$, a planar, connected graph with cycles, Prove: $|E| \leq \frac{s}{s-2}(|V|-2)$. $s$ is the length of smallest cycle

Given $G = (V,E)$, a planar, connected graph with cycles, where the smallest simple cycle is of length $s$. Prove: $|E| \leq \frac{s}{s-2}(|V|-2)$. The first thing I thought about was Euler's ...
5
votes
1answer
32 views

$n$-vertex $3$-edge-colored graphs with exactly $6$ automorphisms which preserve edge color classes, but permute the edge colors distinctly?

In each of these $3$-edge-colored graphs, there are exactly $6$ automorphisms which preserve the set of edge color classes: (These automorphisms don't necessarily map e.g. green edges to green ...
2
votes
2answers
989 views

Every $k$ vertices in an $k$ - connected graph are contained in a cycle.

Let $G$ be a $k$-connected graph. Meaning, $G$ has no less than $k$ vertices, and for every set of $k-1$ or less vertices, if we remove them from $G$, the graph stays connected (Of course, $G$ itself ...
0
votes
0answers
13 views

Do hamiltonian paths exist on n-valent, simple, connected, planar graphs, where n>2?

I don't know to much about graph theory, so was wondering about the posted question. If it is too much perhaps you may know the answer if n is even? Any help is appreciated. Also, this is my first ...
1
vote
2answers
29 views

Complete Toroidal Graphs

I've seen it referenced that $K_N$ is a toroidal graph for $N \leq 7$. Can anyone supply a proof (source link or outline) that $K_8$ is not a toroidal graph?
0
votes
1answer
14 views

Prove that a directed tree does not have a path from a descendant to its parent

Prove: Let T = (V, E) be a directed tree. If v is a vertex of V and u is a descendant of v, then there is no path from u to v. My idea is that if u is a descendant of v, then there exist a path from ...
0
votes
0answers
15 views

N-clique and n-clubs in the figure

I have a small doubt in this figure. What would be a 2-clique and 2-club in this figure? Is {1,2,3,4,5} a 2 - clique here? I am confused because if I take the sub graph, then 4 and 5 are 3 edges ...
1
vote
0answers
112 views

Average Degree of a Random Geometric Graph

A set of $N$ points are distributed randomly on a unit square with uniform distribution. Two points $\mathbf{p}_i$ and $\mathbf{p}_j$ are said to be connected if $\|\mathbf{p}_i - \mathbf{p}_j\| \leq ...
3
votes
0answers
53 views

$G =(V,E)$ is $k$-connected ($k \geq 2$), prove that for every subset $S \subseteq V $, |S|=k there exists a cycle in $G$ that goes through all of $S$ [duplicate]

I thought of starting from the Menger theorem which says that between every two vertices $u$ and $v$ there are $k$-edge disjoint graphs. So I think if I look at $G$ without the subset $S$ then I have ...