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
3answers
185 views

Numbers of ways $k - 1$ edges to be added to $k$ connected components to make the graph connected

Given a graph $G$ with $n$ vertices and $m$ edges. Let us say it has $k$ connected components. Find out how many numbers of ways you can add $k - 1$ edges to make the graph connected. Is it any ...
1
vote
1answer
108 views

Number of 2n-1 equal size partitions up to symmetry

Consider the $K_{2n}$ (or just the set $\{1,\dots,2n\}$) with $S_{2n}$ acting on the vertices. Moreover consider a collection of 2n-1 partitions of the vertices into two equal sized sets (repeated ...
1
vote
1answer
31 views

Is there a proper name for a directed graph with one source and one destination?

The question says it all. Is there a name for a specific type of directed graph which contains only one source and one destination?
1
vote
1answer
202 views

Generalized geography in a directed graph with a perfect matching

Greography is a game where players take turns naming cities. Each city chosen must begin with the same letter that ended the previous city. The game begins with any starting city and ends when a ...
1
vote
1answer
1k views

Proof of König's theorem

Let $G=(V,E)$ be a graph. $H\subseteq V$ is called a vertex cover of $G$ iff $(u,v)\in E\Rightarrow u\in H\vee v\in H$. Now let's assume $G$ is bipartite, i.e. $V=V_1 \cup V_2$ and $E\subseteq ...
1
vote
1answer
78 views

Graph Isomorphism property

I just started a graph theory course, and my very first homework problem is the following: If $ G \cong H $, show that $v(G) = v(H)$ and $e(G) = e(H)$. This is confusing to me, because (I think) ...
1
vote
1answer
198 views

Ramsey Number for Star graphs

For two graphs $H_1$ and H2, the Ramsey number $r(H_1, H_2)$ is the minimum number r so that in any red-blue coloring of the edges of the complete graph Kr on r vertices there is necessarily either a ...
1
vote
1answer
60 views

Claw free Graph

I have been reading this wiki article on how to find if the graph is claw-free or not but I cannot understand some part of it. Algorithm says(Under the recognition title) "...one can test whether a ...
1
vote
2answers
340 views

Perfect Matching in a non-bipartite graph

I need to find out if you can have a perfect matching in a given graph, with $n$ vertices and $m$ edges and $1\leq n,m\leq 100$. I want a complexity of $O(n)$ if possible. I only need to know if there ...
1
vote
2answers
35 views

detecting dynamic parts in graph

I have set of (x,y) points which can be connected to form a graph, my goal is to detect dynamic parts of this graph. by dynamic I mean ranges where the values are not stable but they are changing by ...
1
vote
1answer
53 views

A probabilistic problem in graphs

Let $G$ be a (simple) graph. Each edge will be deleted or will be reminded with probability $\frac 12$ (independent from the other edges). Let $P_{AB}$ be the probability that (after this process) the ...
1
vote
2answers
76 views

What is the equivalent of Delaunay tringulations in high dimensions?

For 2D manifolds, Delaunay triangulation is a very useful tool for coarse graining. It has the nice property that in the flat/euclidian manifold case, it reduces to a 2D simplicial tesselation of the ...
1
vote
1answer
23 views

Explanation of proof about elementary properties of graphs needed.

I've come across a following document with the proof that interests me, unfortunately I'm not able to follow it. The proof is here. I completely don't get what's so contradictory about the last ...
1
vote
1answer
88 views

Gauss Elimination for Colorability Problem

Consider the following system of linear equations modulo 2: $A.X + B.Y = Z, $ where $A$ is a non-singular(modulo 2) $n$ x $n$ boolean matrix, $B $ is $n$ x $m$ boolean matrix, $X$ is n-dimensional ...
1
vote
1answer
104 views

Calculate a determinant related to permutation matrix

Let $ M$ be a permutation $n \times n $ matrix and $[\lambda_1,\lambda_2, \ldots,\lambda_n]$ be the cycle type of the corresponding permutation, i.e. $ \lambda_i$ is the number of cycles of the ...
1
vote
1answer
60 views

How to Prove that a 3-regular bridgeless graph has perfect matching? [duplicate]

Proove that a 3-regular bridgeless graph has perfect matching?
1
vote
1answer
83 views

Aplanar covering of $S^1 \vee S^1$?

Can someone provide an aplanar covering of $S^1 \vee S^1$? What if I insist on it being finite degree? (This question is motivated by the diagram in the first chapter of Hatcher's Algebriac Topology, ...
1
vote
2answers
70 views

Is it possible to draw a graph that has an Euler Cycle but not a Hamilton Path?

Is it possible to draw a graph that has an Euler Cycle but not a Hamilton Path? It seems every Euler cycle I draw has a Hamilton Path.
1
vote
1answer
58 views

Is it possible to draw a graph with a Hamilton Path but not a Euler Cycle?

Is it possible to draw a graph with a Hamilton Path but not a Euler Cycle? It seems that every graph I draw has a Hamilton Path.
1
vote
1answer
69 views

What is the proof that $\sum \limits_{v \in V} deg(v) = 2|E|$?

My textbook gives $\sum \limits_{v \in V} deg(v) = 2|E|$ and has the proof If an edge is not a loop it gets counted twice b/c it's incident with 2 different vertices. If an edge is a loop, by ...
1
vote
1answer
43 views

Vertex coloring proof question

There is a graph $G$ such that if any pair of vertices is removed, then its chromatic number decrease by $2$. Show that $G$ is complete graph.
1
vote
1answer
65 views

Ratio of vertices to edges when airplaines can fly from 1 of 4 cities to any other of the 4 cities

This is a true of false question: There are direct (nonstop) flights amount four cities that make it possible to get from any city to any other city by air. It follows that the beta index of the ...
1
vote
1answer
253 views

Uniqueness of doubly stochastic matrix descomposition

this is my first question in the site. Thanks in advance for all answers. It is well known that each bistochastic matrix can be represented as a convex combination of permutation matrices. I am ...
1
vote
1answer
104 views

Minimum a-z flow and minimum capacity a-z cut

Hi! I am working on a Graph Theory problem. I was wondering when finding flow paths are you allowed to have a path that goes against the directed arrow of the graph? I was wondering if I could have ...
1
vote
1answer
51 views

Bounds on the size of the arc set of a directed graph which is connected but not strongly connected

An exercise in Introduction to Graph Theory by Robin J. Wilson asks for a proof that, if $D$ is a simple directed graph with $n$ vertices and $m$ arcs which is connected but not strongly connected, ...
1
vote
2answers
1k views

How many four-vertex graphs are there up to isomorphism;

Let us call graphs $G = (V,E)$ and $G' = (V', E')$ fundamentally different if they are not isomorphic. How many fundamentally different graphs are there on four vertices? This is a question on my ...
1
vote
1answer
97 views

Of Face and Circuit Rank

The circuit rank of a graph $G$ is given by $$r = m - n + c,$$ where $m$ is the number of edges in $G$, $n$ is the number of vertices, and $c$ is the number of connected components. ...
1
vote
1answer
79 views

Number of $r$-regular, triangle-free graphs of order 100

I would like to find a formula for the number of $r$-regular, triangle free graphs of order 100 where every non-adjacent pair of adjacent vertices has $a$ common neighbors. There is one special case ...
1
vote
3answers
251 views

Show that there is exactly one maximal element in a poset with a greatest element?

This is true, any idea how to say it in proof form? I would guess: In a poset with one maximal element, then that element has no other elements above it and has elements below it. If its the only ...
1
vote
1answer
81 views

Heat equation for a finite graph

Thank you for an interesting website. I would like to construct the heat equation for a finite graph $G$ using basic math concepts. For example, if $G = \mathbb{Z}/m\mathbb{Z}$ then I think of $G$ ...
1
vote
1answer
211 views

Explicit formula for exponential objects in category of digraphs

I have already asked a similar question: Exponential object in a category of graphs but earlier I have asked only about existence of exponential object, while in this question I ask for exact formulas ...
1
vote
1answer
116 views

Non-isomorphic simple graphs: order $n$, size $\displaystyle \frac{na}{2}$, degree sequence $(a,a,a,…,a) \in \mathbb{N}^n$

If a simple graph has order $n$, size $\displaystyle \frac{na}{2}$ and degree sequence $(a,a,a,...,a) \in \mathbb{N}^n$ then is it unique up to isomorphism? I thought of this question while ...
1
vote
1answer
128 views

Another condition for bipartite graphs

Let $G$ be a graph. Then prove $G$ is bipartite if and only if for all subgraphs $H$ of $G$ with no isolated vertices. $\alpha(H)=\beta'(H)$. Here $\alpha(H)$ is the size of the largest independent ...
1
vote
1answer
69 views

Graph walking: smallest set of “blocking” nodes

I'm not sure I've got the terminology right in my question, but here's conceptually what I'm looking for. In a directed acyclic graph with a single root node and multiple end nodes, how can I can ...
1
vote
1answer
49 views

Prove a graph can be partitioned into two groups where every vertex has half its edges cross?

I'm trying to show that for any graph with more than 2 vertices, the graph can be partitioned into two groups such that for every vertex at least half of the vertices its connected to are in the other ...
1
vote
1answer
40 views

Show that a bi-partition number of edges, |{st ∈ E|s ∈ S, t ∈ T}| ≥ |E|/4

I have this exercise: Given an oriented graph G = (V, E), with at least 2 vertices, prove that you can build in polynomial time a bi-partition (S, T) (S ∪ T = V, S ∩ T = ∅, S, T != ∅) so that |{st ∈ ...
1
vote
1answer
110 views

Combinatorics Graph Theory Proof problem

I am struggling with 9.31 from A Walk Through Combinatorics by Miklos Bona. The problem statement reads: There are several people in a classroom; some of them know each other. It is true that if ...
1
vote
2answers
251 views

Regular graph (Homework)

Let $G = (V, E)$ be a graph and $ad(G) = \frac{2|E|}{|V|}$ the average degree of $G$. $$ mad(G) = max ( ad(H) : H \le G ) \text{ the maximum average degree of a subgraph of $G$} $$ We know that ...
1
vote
1answer
88 views

Number of branchings on {1,…,n}

A branching is a digraph G, such that the indegree of every vertex is at most 1 and the underlying undirected Graph has no cycles. Show that there are $(n+1)^{n-1}$ branchings on the set of vertices ...
1
vote
1answer
93 views

Find self-avoiding-filling-polygon represented by system of linear equations

In Euclidean graph where each vertex is a point on the $2D$ plane, so the weight of each edge is the Euclidean distance between the vertices. I want to find self-avoiding-filling-polygon from my graph ...
1
vote
1answer
52 views

Graph Ramsey Theory for Multiple Copies of Graphs

I had the following question from Graph Ramsey theory. Show that if $m \geq 2$, then $$ R((m+1)K _{3},K _{3})\geq R(mK _{3},K _{3}) + 3. $$ Thanks.
1
vote
1answer
35 views

Does the Prim algorith always create the same tree despite the starting node?

Does the Prim algorith always create the same tree despite the starting node? PD: sorry for my english.
1
vote
1answer
68 views

How can knowing the *number* of strongly connected components of a directed graph help us detect its cycles?

I understand that when you know the strongly connected componentes of a directed graph, it can help us detect the cycles of the graph, as all the cycles will occur in each SCC. But how can just ...
1
vote
1answer
127 views

Prove that these lines are perpendicular (orthogonal)…

According to the Law of mathematics, the product of slopes of $2$ perpendicular lines has to be $ -1 $. Then, how do you prove that the following lines are perpendicular. $x=4$ , $y=6 $ My ...
1
vote
1answer
30 views

Number edges of 3-regular graph so that every vertex has a 0,1, and 2 edge

Let's say you have a graph such that every vertex has exactly 3 edges. You try to number every edge of the graph with either a 0, 1, or 2 so that every vertex has exactly one of each type of edge. Is ...
1
vote
1answer
157 views

Spectrum of the adjacency matrix of strongly regular graphs

I am working through a proof of the following Theorem: Let $G$ be a connected, $k$-regular graph, $G\neq K_n$, then $G$ is strongly regular if and only if $|Spec(G)|=3$. Now I am having trouble with ...
1
vote
2answers
208 views

Induced subgraphs (graph theory)

I have the following graph theory question that I am stuck on: Prove or disprove: For every graph G and every integer $r \geq \text{max} \{\text{deg}v: v \in V(G) \}$ , there is an r-regular graph H ...
1
vote
2answers
24 views
1
vote
1answer
88 views

Making minimum number of partitions of a set

Let us consider a set in which every element has an ordered pair of natural number (x,y)( Each pair is distinct) associated with it. Let us define a partition of a set to be consisting of elements ...
1
vote
1answer
32 views

Give examples of polytopes $\Delta$ in $\mathbb{AR}^3$ such that

With Sym $\Delta$ of the set $\Delta$ consisting of all isometries of $\mathbb{AR}^n$ that map $\Delta$ onto $\Delta$, Sym $\Delta$ acts transitively on the set of vertices of $\Delta$ but is ...