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

0
votes
0answers
5 views

Number of Vertices with $\mu$ Common Neighbor

$\mathcal{G}$ is a graph class. Each graph $G$ of $\mathcal{G}$ has the following properties- $G$ is a $k$ (variable with respect to different graphs) regular graph of $n$ vertices. The vertex set ...
1
vote
0answers
19 views

Derive Hall's theorem from Tutte's theorem

I'm trying to derive: Hall Theorem A bipartite graph G with partition (A,B) has a matching of A $\Leftrightarrow \forall S\subseteq A, |N(S)|\geq |S|$ From this: Tutte Theorem A graph G has a ...
0
votes
0answers
5 views

Finding δ(s,v) for all v∈V , when given zero weighted cycle edges- in linear time

Formally: Let it be $G=(V,E)$ directed graph with a weight function $w: E -> R $. Let it be $s∈V$ (source vertex). For all $e∈E$ so that $e$ belongs to a cycle in G, $w(e)=0$ (if $e$ doesn't ...
1
vote
1answer
5 views

Duality theorem between Cycle Space and Cut Space in terms of Matrices?

The book Graphs and Matrices by Bapat formulates linear algebra on graph theory, yet I cannot find important theorems such as Duality theorem between the cycle space and the cut space (Diestel p.26, ...
1
vote
1answer
35 views

Graph with exactly one perfect matching

How do I prove that if $ G $ graph, with $2n$ vertices, has exactly one perfect matching then $ |E(G)| \le n^2 $ ?
1
vote
0answers
13 views

The existence of a cycle in a graph

Let C and D will be different cycles in the graph G, and e - common edge to the cycles of C and D. Show that a graph G contains a cycle not passing through the e. I think, it's not easy task, because ...
0
votes
0answers
12 views

$k$-regular connected graph with no perfect matching

How do I construct a $k$-regular connected graph with no perfect matching? I know that if $G$ is $k$-regular bipartite graph it has perfect matching, so the graph that I'm looking for shouldn't be ...
0
votes
0answers
24 views

Propositional formulas for connected graph

I have some difficulties with the following problem. Let $G=(V,E)$ be a graph with $V=N$ (natural numbers) and $p_{ij}$ a set of propositional variables for which we have $p_{ij}$ is true <=> ...
0
votes
2answers
13 views

Is this triangulation consistent with Sperner's Lemma?

Since any two triangles which intersect have an edge or a vertex in common, the triangulation is simplicial. However, I am concerned about triangle $A$. Is every sub-triangle supposed to have a ...
0
votes
0answers
11 views

Upper bound for a graph related finite sum

At the moment I am looking into undirected graphs $G=(V,E)$ with node set $V=\{1,\ldots,M\}$ and edge set $E$. We can assume that they are connected by the way. Lets denote edges from $i$ to $j$ by ...
2
votes
2answers
31 views

Construct a non-Hamiltonian Graph

How do I constuct a $G$ non Hamiltonian graph for any $n≥3 $ $( |V(G)|=n )$, in which $\delta(G)$ is at least $(n-1)/2$? Is there any algorithm for that? Do I have to use mathematical induction? When ...
1
vote
1answer
36 views

Describe 3-colourable graph in propositional calculus

I am trying to solve the following problem. Let $G=(V,E)$ be a Graph with $V=N$ (natural numbers) and $p_{ij}$ a set of propositional variables for which we have $p_{ij}$ is true <=> $(i,j)\in E$. ...
0
votes
0answers
41 views

Prove that the set of matrices $\{I,A,A^2,\ldots A^m\}$ is linearly independent.

Let $A$ denote the adjacency matrix of a connected graph $G$ with $n$ vertices and $e$ edges.If $i $ and $j$ are vertices of $G$ with $d(i,j)=m$. Then prove that the set of matrices ...
1
vote
1answer
20 views

How do I rearrange an adjacency matrix of an acyclic digraph so its non-zero elements are above the diagonal?

Any graph can be represented by an adjacency matrix. The matrix for an acyclic digraph can be represented as a matrix with all its non-zero elements above the diagonal. However, if I were to take an ...
1
vote
0answers
27 views

Clarification of Sperner's Lemma

From Graph Theory by Bondy, Murty Image from wikipedia I don't see how the picture holds according to the definition from the Graph Theory book. Specifically, the definition says to assign ...
1
vote
0answers
11 views

Deletion-contraction versus addition-identification

Short version: there are two common formulas for computing the chromatic polynomial of a graph. They go by the names, deletion-contraction and addition-identification. They are equivalent, ...
0
votes
0answers
16 views

Minimum number of paths needed to enforce an Eulerian Path

Given a graph $G$ with at least 1 Eulerian Path (a path that travels every edge exactly once). I would like to find the minimal number of edges that, if traversed as a Trail (an edge is never ...
0
votes
1answer
20 views

Show that if $u, v \in V(G)$, $u \not= v$, with $G$ a $k$-critical graph, then $N(u) \not\subseteq N(v)$

I tried considering $\chi(G-u) = k-1$ and using the same for $v$, And when I quit a vertex $u$ or $v$ I make a proper partition in $k-1$ color classes, saying that this differ in one the color of ...
0
votes
1answer
9 views

Relation between size and order of a graph k- chromatical critical

How can i prove the following statement? Let $G$ be a graph k-critical of order = $n$ and size = $q$. Show that $k \le \frac{2q + n}{n}$
0
votes
1answer
18 views

Disjoint paths in a directed graph

Suppose you have a directed graph $G=(V,E)$. For all $v\in V$ the number of edges going into $V$ is equal to the number of edges out of $V$. Assume that vertices cannot have edges pointing to ...
0
votes
0answers
13 views

Lower bound algorithm of the Travelling Salesman Problem; does it matter which node we delete?

Above is the algorithm I'll be referring to if you didn't know what I meant. The fact that it states "choose and arbitrary node" implies that no matter what node we choose to delete, we should get ...
0
votes
1answer
36 views

Total Chromatic Number of Cycles

According to Wikipedia, In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be ...
1
vote
2answers
29 views

Prove that a simple graph $G$ on $n$ vertices that contains no $K_{2,3}$ has at most $n^{3/2}$ edges.

For each vertex $v_i$, let $N(v_i)$ denote the set of neighbors of $v_i$. Because $G$ does not contain $K_{2,3}$, equivalently we have $|N(v_i) \cap N(v_j)| \leq 2$ for any $i \neq j$. We need to ...
1
vote
1answer
14 views

For every simple graph like $G$ , $\chi(G) \le {(2e)}^{\frac{1}{2}}$

$\chi(G)$ The chromatic number of a graph is the smallest number of colors needed to color the vertices of so that no two adjacent vertices share the same color. Now the question : Assume that $G$ ...
0
votes
0answers
5 views

Sparse subgraph preserving distance for n source-destination pairs (s_i,t_i)

We are given a directed graph G with vertex set V(G)={s_1,s_2,..,s_n, t_1,t_2,..,t_n}. So G has a total of 2n vertices. Our aim is to compute sparse subgraph H of G such that distance from s_i to t_i ...
0
votes
1answer
18 views

If every vertex in a graph G has degree >=d, then show that G must contain a circuit of length at least d+1. (Applied Combinatorics, 1.5.8)

There are two questions that essentially asked the same thing. One is categorized as a repetition but I just don't feel the other one's answers are valid. Let $G$ be a graph of minimum degree ...
1
vote
0answers
13 views

A retract H of G is an induced subgraph of G. show that it is isometric.

Let G and H be graphs. A homomorphism φ : G → H is a map φ : V(G) → V(H) which preserves edges, that is, {x, y} ∈ E(G) ⇒ {φ(x), φ(y)} ∈ E(H). We write G → H if there is a homomorphism φ : G → H. Let ...
0
votes
1answer
26 views

Upper bound on the list chromatic number of $d$-degenerate graphs

It can be proved that $\chi(G)\le d+1$ if $G$ is $d$-degenerate, but can we also say that $\chi_\ell(G)\le d+1$, in general[note 1]? Here, $\chi(G)$ is the chromatic number of $G$ and $\chi_\ell(G)$ ...
0
votes
0answers
8 views

“Anti-critical” or “Robustly” Chromatic Graphs

A graph G is "critically k-colourable" if the chromatic number of G is k, but if any vertex is removed, the chromatic number is k-1. But we can also talk about the opposite situation, where a graph ...
0
votes
0answers
10 views

Asymptotic Density of threshold graphs

Someone said yesterday "threshold graphs are really scarce". Now, there are a lot of graph classes that occur with probability 0, in random graphs. How would someone make meaningful statements about ...
0
votes
1answer
17 views

Sum of squares of eigen values of adjacency matrix is equal to twice the number of edges

Let $A$ denote the adjacency matrix of a graph $G$ with $n$ vertices and $e$ edges. Let $\lambda_1\ge \lambda_2\ldots \ge \lambda_n$ be the eigen values of $A$ . Show that : $\sum_{i=1}^n ...
0
votes
1answer
39 views

How many copies of P3 are there in K10

How many copies of P3 are there in K10? I can draw both of the graphs, but I don't know how you calculate this and assume there is a method that can be used to make this easier. Thanks
0
votes
1answer
14 views

the relation between degree of the node and it's adjacent nodes

Does the same degree of two nodes in two isomorphic graph respectively imply that the adjacent nodes around these two nodes are the same. too?
2
votes
1answer
13 views

show that if two trees have isomorphic line graphs , they are isomorphic.

i want to use Whitney isomorphism theorem : if the line graphs of two connected graphs are isomorphic , then the underlying graphs are isomorphic. except in the case of the triangle graph K3 and K1,3 ...
1
vote
1answer
25 views

Adjacency matrix of the complement of a graph

I read a lemma. $J$ is the all ones $n \times n$ matrix, $I_n$ is the $nxn$ identity matrix. Let the adjacency matrix of a simple graph $G$ on $n$ vertices be $A = A(G)$. Then the adjacency matrix ...
1
vote
1answer
10 views

Vertex Cosine Similarity of a weighted graph

I'm trying to calculate the vertex cosine similarity of a weighted directional graph, however struggling to understand the concept. While I understand the methodology for simple and directed graphs, ...
1
vote
0answers
32 views

Prove if $G $ and $H $ are graphs on the same vertex set, then $dg(G \cup H) \leq dg(G) + dg(H)$ [on hold]

Prove if $G$ and $H$ are graphs on the same vertex set, then $dg(G \cup H) \leq dg(G) + dg(H)$ $dg(G) $ is the the minimum $k $ such that $G $ is $k $-degenerate. I know it can be proved with ...
1
vote
1answer
17 views

Find the adjacency matrices for $K_n$ and $W_n$

Find the adjacency matrices for $K_n$ and $W_n$. The adjacency matrix $A = A(G)$ is the $n\times n$ matrix, $A=(a_{ij})$ with $a_{ij}=1 $ if $v_i$ and $v_j$ are adjacent, $a_{ij}=0$ otherwise. ...
0
votes
0answers
26 views

The maximum number of matching iterations

Let $G = (L, R, E)$ be a complete bipartite graph, where $L$ and $R$ are disjoint sets of vertices. Let $|L| = n, |R|=m$, where $n < m$. The algorithm consists of several iterations and in each ...
2
votes
1answer
16 views

Find a connected graph that has exactly $2$ cutpoints of order $2$ and $3$ cutpoints of order $3$

Find a connected graph that has exactly $2$ cutpoints of order $2$ and $2$ cutpoints of order $3$ Definition: A cut point of order $k$ is a point $a \in X$ whose complement $X-\{a\}$ consists of ...
1
vote
0answers
26 views

Probability that a random bipartite graphs is the intersection of simple cycles

I have the following problem and honestly i don't know how to start working on it. Any clue will be appreciated. I need to calculate the probability that following the Erdos-Renyi model, a random ...
9
votes
1answer
54 views

How do you calculate the smallest cycle possible for a given tile shape?

If you connect together a bunch of regular hexagons, they neatly fit together (as everyone knows), each tile having six neighbors. Making a graph of the connectivity of these tiles, you can see that ...
0
votes
0answers
10 views

How to estimate the duration of the path?

Let $G=<V,E>$ $p$ - sequence of vertices and edges For each edge $(u,v)\in E$ there is information about the transition time from $u$ to $v$ represented as a set of values $T=\{t_0, t_1, ... ...
0
votes
1answer
17 views

Find the spectrum of graph

Find the spectrum for the following graph by calcuation The spectrum of a graph $G$ is a list of the eigenvalues and the multiplicities of the eigenvalues of the adjacency of matrix $A$ of $G$. ...
1
vote
1answer
17 views

Calculate the number of paths found on the basis of probabilities

Let G=<V,E> - weighted directed graph $w(e_{ij})$ - transition probability from node $v_i$ to node $v_j$ ($w \in[0;1]$) So my first question is: how ...
0
votes
0answers
65 views

Algorithm to calculate shortest time in which two people can collect K items from N cities.

There are N cities connected via M bidirectional roads. Each road connects exactly 2 different cities and has a travel time associated with it. There are K different items in these cities. Given the ...
1
vote
0answers
41 views

Spencer and Shelah zero-one law for Erdos-Renyi random graph $G(n,p)$

In Erdos-Renyi random graph $G(n,p(n))$; set $p(n)= (\frac{ln n}{n})^2$. We know that already Spencer and Shelah have proved that zero-one law doesn't hold for $p(n)= \frac{ln n}{n}$. Now the question ...
3
votes
1answer
80 views

For which $n$ is the $n$-dimensional hypercube a planar graph?

I've been asked the following question: For which values of $n$ is $Q_n$ a planar graph, where $Q_n$ is the $n$-dimensional hypercube? I succeeded to prove that for $n$ equal or greater than $6$ it ...
1
vote
0answers
17 views

I am not able to label the vertex of the following graph in mathematica, can some one please help me.

Graph[{1, 2, 3, 4, 5, 6}, {1 -> 2, 1 -> 3, 2 -> 5, 2 -> 6, 5 -> 6}, VertexLabeling -> True] Graph::optx: Unknown option VertexLabeling in ...
1
vote
1answer
26 views

Chromatic number of Erdos-Renyi random graphs $G(n,m)$

In Erdos-Renyi random graphs $G(n,m)$, set $n=4$ and $m=5$. The question is as follows: What is the probability for to having Chromatic number exactly 2 in the case of $G(4,5)$; in other words what ...