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
vote
0answers
42 views

Adjacency matrix of $\bar G $

Let $M$ be the all $n \times n$ matrix and $I_n$ be the $n \times n$ identity matrix. Suppose $A$ is the adjacency matrix of a simple graph $G$ on $n$ vertices. Find the adjacency matrix of $\bar ...
1
vote
1answer
31 views

Find total number of ways to disconnect the following graph

Find total number of ways to disconnect the following graph: $4$ $5$ $6$ $8$ My attempt: I've done manually to find possible disconnected sets of given graph. I guess it is should be ...
-2
votes
0answers
19 views

Example of barabasi albert's preferential attachment model and generalized random graphs [on hold]

I have a graph having some 10,000 nodes and 90,000 edges. Now i want to implement and generate random graphs as the same number of nodes and edges and want to compare my original graph with random ...
1
vote
1answer
18 views

How to improve my proof and whether or not one condition in the statement is important in writing the proof?

A simple graph $G$ is connected iff for every partition of the vertices into two non-empty sets $X$ and $Y$, there is a vertex $x\in X$ and a vertex $y\in Y$ such that $xy$ is an edge of $G$. My ...
-1
votes
0answers
7 views

Disjoint paths in a digraph

I have a digraph such as every vertex in it has the same amount of edges coming in and out. So, if for a pair of vertices (x and y) there are k > 0 edge-disjoint paths that go from x to y. Can I ...
2
votes
1answer
33 views

Relation between Adjacency Matrix and Incidence Matrix

Let the Adjacency matrix be A, and Incidence Matrix be B; 'd' represents degree of given vertex How do we prove $B.B^T=A+\begin{bmatrix}d(V_1) & 0 &\dots \\ 0 & d(V_2) & 0 & ...
0
votes
1answer
31 views

Find the spectrum of graphs for adjacency matrix

Find the spectrum of graphs for adjacency matrix $(A)$ below : $$ \left[ \begin{matrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 ...
0
votes
0answers
7 views

Algorithm to test if a given Graph has a unit distance representation in the plane

Like stated above. A Google search revealed only that the problem is NP hard but not if an algorithm (even a terribly slow one would be sufficient) is known.
3
votes
1answer
45 views

Threshold probabilities in Erdos-Renyi random graph model $G(n,p)$ and intermediate value theorem

In Erdos-Renyi random graph model $G(n,p)$, set $Q$ any graph property. Suppose there exist $p_1(n)$ and $p_2(n)$ in $(0,1)$ for $n \in \mathbb{N}$ such that $Pr(G(n,p_1)\ \text{has property}\ Q) ...
1
vote
0answers
12 views

DAG descendant vertices tag sum

Hello I have a DAG with a tag per vertex. I want to write an algorithm to compute a per-vertex sum of the descendant vertices tags counting only once the repeated ones. Tracking visited vertices ...
1
vote
0answers
21 views

forbidden chromatic polynomial

We wish to show below chromatic polynomial are not exist; It means that we couldn't find any graph that has one of these chromatic polynomial 1- $\ k^5 - 4k^4 + 8k^3 - 4k^2 +k$ 2- $\ k^4 - 3k^3 + ...
0
votes
2answers
25 views

Check my proof on showing a graph with each vertex's degree at least $e$ has every tree with $e$ edges a subgraph

Let $T$ be a tree with $e$ edges and $G$ be a simple graph such that ech vertex has degree at least $e$. We need to show that $T$ is a subgraph of $G$. I tried to prove this by induction. The base ...
2
votes
0answers
34 views

Genus of the union of three complete graph each isomorphic to $K_5$.

Suppose $G_1,G_2,G_3$ are three graphs each isomorphic to $K_5$. Suppose $V(G_1)=\{1,2,3,4,5\}$, $V(G_2)=\{1,2,6,7,8\}$ and $V(G_3)=\{1,2,9,10,11\}$. What is the genus of the graph $G=G_1\cup ...
1
vote
0answers
59 views

Twisty Puzzle Solving Program

I'm writing a program to help me solve a twisty puzzle. In this case it's the face-turning octahedron. I'm representing the puzzle as a group with face twists as generators. The facelets are in a list ...
14
votes
1answer
682 views

Is it really impossible to lose the Hydra game?

In a number of blog posts I found the claim that the game described below cannot be lost, which is to say, every possible strategy is a winning strategy. In each case, a sketch proof is given that ...
0
votes
0answers
20 views

Binary operation on Graphs

Are there "binary operations" on graphs, which make the set of all graphs, a commutative ring or a field For example $G_1 \cdot ( G_2 + G_3) = G_1 \cdot G_2 + G_1 \cdot G_3$ By a graph I mean ...
-2
votes
0answers
15 views

Number of SDRs of ${A_1,\dots,A_k}$ whose minimum size of $A_i$ is $k$ [closed]

Suppose that $A_1, A_2, \dots,A_n$ refer to a set system, which the size of minimum of them is $k$ (for any $i$ such that $|A_i|≥k$) this family (set system) has a system of distinct representatives. ...
0
votes
0answers
28 views

What is the meaning of probability of an edge connected by two nodes in a graph

I am studying random graph models. While studying random graph models if we want to generate for instance erdos renyi's random graph model then we will have to place $n$ vertices and connect each pair ...
-1
votes
0answers
17 views

A SDR extension problem [closed]

enter image description here I think we should use induction. for subset I when $|I|=1$ then we have for any $i\in \{1,\dots,n\}$ $|A_i|\leq 2$. Then for any $A_i$ we have $2$ SDR. then we suppose ...
9
votes
1answer
144 views

Application of Combinatorics/Graph Theory to Organic Chemistry?

Recently, I have been self-teaching graph theory and having an organic chemistry course at school. When I was learning isomer enumeration I found great resemblance between organic molecules and ...
0
votes
0answers
14 views

Prove that if $G$ is a planar graph of girth at least $6$, then $\chi (G) \le 3$. [duplicate]

I know that the sum of the degrees is equal to $2e \le 3n-6$. How do I prove the claim using that piece? I've already proven that $|E(G| \le \frac {3}{2}(n-2)$ and I've been told this is also useful ...
3
votes
0answers
34 views

Isomorphism of Non-Symmetric Matrix when Permutation-Set is given: A simple observation

Context: Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not ...
1
vote
1answer
40 views

Let $W_n$ be the wheel graph on $n+1$ vertices. Find $χ(W_n;k)$. [duplicate]

The first thing I did was I drew $W_6$. Now how do I find the chromatic number of that and what is $k$?
0
votes
0answers
34 views

Assume that $|V | = |E| + 1$ and that $G$ is connected. Prove $G$ is a tree. [duplicate]

Let $G = (V, E)$ be a finite graph. (A) Assume that $|V | = |E| + 1$ and that $G$ is connected. Prove $G$ is a tree. (B) Assume that $|V | = |E| + 1$. Find an example that $G$ is not a tree.
2
votes
0answers
12 views

Bounds for the coefficients of the characteristic polynomial of a graph

Let $G$ be a $n$-vertex graph and $A_G$ its adjacency matrix with charachteristic polynomial $$p_G(x) = x^n + a_1 x^{n-1} + \cdots + a_{n-1}x + a_n\,. $$ It is well known that $$(-1)^i a_i = \sum ...
0
votes
2answers
38 views

Show that if any two odd cycles of G have a vertex in common, then $\chi(G)$ <= 5 [closed]

A vertex coloring is an assignment of labels or colors to each vertex of a graph such that no edge connects two identically colored vertices. The most common type of vertex coloring seeks to minimize ...
3
votes
2answers
37 views

Could anybody please check my proof about connected graph?

I have written a proof of the following statement but not sure whether it is correct or not. Let $G$ be a connected graph and each vertex has even degree. Show that if we remove ANY edge of the graph ...
0
votes
0answers
18 views

Edge disjoint circuits from Complete graph

Problem: Given a complete graph Kn with greater than n*r edges where r>=1 and n>=3, n>=2r+1. Can we make r number of edge disjoint n-circuits beginning and ending in the same vertex from Kn. Note: It ...
2
votes
1answer
18 views

Prove that $L=C^T C-2I$

The incidence matrix $C$ of a graph and adjacency matrix $L$ of its line graph are related by $L=C^T C-2I$ I know this property from this site. I understand how to do calculation by $L=C^T ...
-1
votes
0answers
10 views

How do I find the crossing number of $\overline Q_3$?

For one thing, I know that $\overline Q_3$ is nonplanar. The problem is, how do I find the crossing number for this hypercube graph?
3
votes
1answer
59 views

Limit probability of a complete bipartite random graph $G(n,n,p)$ is connected

I need to calculate the following probability limit for a complete bipartite random graph $G(n,n,p)$ in the Erdos-Renyi model: \begin{equation} \lim_{n\rightarrow\infty}\mathbb{P}[G(n,n,p) \text{ is ...
1
vote
0answers
20 views

Enumerate out-trees that include a set of nodes in a directed graph

Given a digraph A, and an N set of nodes in the digraph. I need to enumerate the set of out-trees that contain those nodes. Where all the the out-trees leaves terminate on a node in set N. As a ...
0
votes
2answers
35 views

How many cycles does a connected graph on 2015 vertices and exactly 2015 edges contain?

I understand that one possible answer is $1$ cycle because you can just have a path of $2015$ vertices ($e = n-1$, where $n$ is the number of vertices) and connect the last vertex with the first ...
1
vote
1answer
29 views

Let $G$ be a $k$-regular bipartite graph, $k \ge 2$. Prove that every edge of $G$ appears in some perfect matcing in $G$. Is this proof correct?

Using Hall's Theorem, there could only be a perfect matching when the set of $|A|$ vertices have the same number of vertices as set $|B|$, and that there is a subset of vertices $|U|$ in $A$ that is ...
0
votes
1answer
18 views

In a directed graph with n≥2 nodes, if two different nodes reaches every nodes (including itself), then this graph is strongly connected.

I think this statement is true because if node a can reach every node (including node b) and node b can reach every node (including node a), there is an edge between node a and node b. This means that ...
0
votes
0answers
13 views

Algorithm for finding all maximum out-trees in a digraph

If we have a directed graph, and the graph contains subgraphs which are out-trees. We could find the set of out-trees, such that it does not contain any out-tree that is contained by another out-tree. ...
0
votes
2answers
43 views

Prove $G$ has at most $n^2$ edges.

If $G$ is a graph on $2n$ vertices that has exactly one perfect matching. My understanding is to add one more edge and then prove there are two perfect matchings, but it seems hard to prove ...
0
votes
0answers
10 views

Reducing a graph without lowering its chromatic number

While trying to find an algorithm to reduce a graph without lowering its chromatic number, I made the following algorithm (but not sure if it works): Given a (simple) graph $G$, look for subgraphs ...
4
votes
2answers
54 views

Why does the Number of Graphs on $n$ Vertices Blow up so Quickly?

See for example here: https://en.wikipedia.org/wiki/Graph_enumeration I would have thought (naively) that the number of graphs on $n$ vertices would only grow as $\mathscr{O}\left( _nC_2\right)$, but ...
0
votes
1answer
35 views

How to fill in the gaps in my proof to make it more convincing?

Let $T$ be a tree with $3$ edges. Let $G$ be a simple graph such that each vertex has degree at least $3$. Show that $G$ has $T$ as a subgraph. This statement is obvious but I am not sure how to ...
-1
votes
1answer
20 views

HW Question about the Eccentricity of connected graphs. [closed]

How do I prove the following Theorem?: "Let G=[V,E] be connected graph with n vertices, therefore: rad(G)<=Diam(G)<= 2 * rad(g).
-1
votes
0answers
14 views

Vertex-cover-like problem with reduction to maximum flow

I am trying to solve the following problem: Solve the following problem by reducing it to the computation of a maximum s-t-flow: Let G be an undirected graph, $c:V\rightarrow\mathbb{Z}$ and ...
-1
votes
1answer
47 views

A graph G which can’t be painted properly in 2000 colors

A graph G which can’t be painted properly in 2000 colors (i.e. any two adjacent vertices have different colors) is given. The graph is properly painted in 2016 colors. Prove that a path of length 2000 ...
2
votes
0answers
42 views

In a directed graph with $n \geq 2$ nodes, if two different nodes reaches $n$ nodes, then this graph has a directed cycle.

I think this statement is true because if first node can reaches every other node (including second node) and second node can reaches every other nodes (including first node), then first node and ...
3
votes
1answer
25 views

Determine all maximal planar graphs, where one-third of their vertices have degree $3$, one-third have degree $4$, and one third have degree $5$.

To do this, I have $\frac {1}{3}n = \deg 3$, $\frac {1}{3}n = \deg 4$, and $\frac {1}{3}n = \deg 5$. I also know that $e=3n-6$ where $e$ is the number of edges and $n$ is the number of vertices. I ...
1
vote
1answer
26 views

Show every self-complementary graph on $4k + 1$ vertices has a vertex of degree $2k$.

I am not sure how to show this. I know a self complimentary graph on $4k+1$ vertices will have $\frac{\binom{4k+1}{2}}{2}=4k^2+k$ edges. I think another way to rephrase the problem is to show that ...
1
vote
1answer
31 views

What is a useful starting idea to think about this simple graph problem?

I would like to prove the statement that there are $2^{\binom{n-1}{2}}$ simple graphs are there with vertex set $\{1,\ldots,n\}$ such that every vertex has even degree. The thing that confuses me is ...
1
vote
1answer
13 views

How Many Marriages in a Bipartite Graphs?

Given two disjoint sets, say $M$ and $W$, both of size $n$, I want to compute how many possibilities of marriage exist. For example, when $n=1$, there are two marriages only: either $m_1-w_1$ or ...
12
votes
1answer
94 views

Why is the Topology of a Graph called a “Topology”?

The topology of a graph (i.e. a network topology), as far as I can tell, doesn't actually have anything to do with open or closed sets, nor does it have any consistent, rigorous definition in ...
-3
votes
1answer
21 views

Graph on 2015 vertices [closed]

A) what is the maximum number of edges that a graph on 2015 vertices can have without containing a subdivision of K3? B) How many cycles does a graph on 2015 vertices and exactly 2015 edges contain?