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
12 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 ...
0
votes
2answers
14 views

How to tell if its possible to build a graph based on given info.

For each of the lists below either draw an connected, undirected graph with eight nodes having one node of each degree listed or give a convincing argument why it is impossible. 1)7,7,3,3,3,3,3,1 ...
0
votes
1answer
10 views

Number of unordered cycles of length $3$ in a graph with $n$ vertices.

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is $\frac{1}{2}$. What is the expected number of unordered cycles of length ...
0
votes
0answers
25 views

Bipartite graph with $2 \times 10^{6}$ vertices, I need help with removing edges from the graph.

Let G be a bipartite graph. The number of vertices are equal to $2 \times 10^{6}$. Every node is of degree 10. We remove every edge with Probability $2^{-0,1}$. Show that the number of nodes after ...
0
votes
1answer
9 views

How to estimate the similarity of two DAGs

Given two DAGs $G_1(V,E_1)$ and $G_2(V,E_2)$ over the same vertex set $V$. Is there any well-studied measures to check the similarity between $G_1$ and $G_2$? I know the definition of similar is too ...
1
vote
0answers
12 views

Prove that for every $k \geq 1$, there exist a connected graph $G$ of genus $k$

Prove that for every $k \geq 1$, there exist a connected graph $G$ of genus $k$ Here is what I think the proof should be. Let's represent $S_k$ as a regular $4k$- gon as following Define $H$ to ...
1
vote
1answer
45 views

Estimating sums by integrals

Estimating sums by integrals. Let $f : \mathbb{N}→\mathbb{N}$ be an increasing function. Show that $$\sum \limits_{i=1}^n \frac1{f(i)}<\frac1{f(1)}+\int \limits_{1}^{n}\frac1{f(x)}dx$$ I really ...
1
vote
0answers
10 views

Weakly acyclic games in game theory

I read that weakly acyclic games are more general than potential games. Potential games are said to have a finite improvement property where each player's payoff function is aligned with a potential ...
0
votes
0answers
22 views

Finding neccesary and sufficient condition for uniqness of neighbours on graph

Let $(G,E)=(V_1\cup V_2,,E)$ be a bipartite graph. Find necessary and sufficient condition s.t for every vertex in $V_1$ exist two distinct neighbors from $V_2$. That seems obvious (necessary) ...
5
votes
2answers
64 views

Getting equations from a network graph

I am learning about Network Analysis in Discrete Math and I need help figuring out how to get the equations from this graph: The arrows represent how many particles are going in a given direction. ...
1
vote
1answer
14 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. ...
1
vote
1answer
29 views

What are $r(\Lambda)$ and $s(\Lambda)$?

Proposition 7.2 in Biggs Algebraic Graph Theory book says that $$\det A=\sum (-1)^{r(\Lambda)} 2^{s(\Lambda)},$$ where $A$ is the adjacency matrix of a graph $\Gamma$ and the summation is over all ...
0
votes
1answer
25 views

Prove that the genus $\gamma(G) \leq cr(G)$ for every graph $G$

a) Prove that $\gamma(G) \leq cr(G)$ for every graph $G$ b) Prove that for every $k \geq 1$, there exist a graph $G$ such that $\gamma(G)=1$ and $cr(G)=k$ Let $G$ be any graph . If $G$ is planar ...
1
vote
1answer
25 views

combinatorics digraph question

A digraph $G = G(V,E)$ on the set of vertices $V$ is a graph where every edge $e ∈ E$ is directed. (Note that double arrows are not allowed in a digraph.) How many digraphs on $n$ vertices are there? ...
3
votes
0answers
46 views

Every tree has two leaves. Is my proof ok?

A tree is a connected acyclic graph. A leaf is a vertex of degree one. The distance $d(u,v)$ between two vertices $u$ and $v$ of a graph is the length of the shortest path from $u$ to $v$. Theorem. ...
3
votes
0answers
36 views

Transpose of the adjacency matrix

As homework I had to do an adjacency matrix for the following graph: My solution was the following: $$ \begin{bmatrix} 0&0&1&0&0 \\ 1&0&0&1&0 \\ ...
1
vote
1answer
27 views

Wheel Graphs and Dimension of Embeddings

I'd like to preface this by saying this is the tip of the iceberg for an optional question for a summer REU program application, so if you think asking this question is in bad taste, let me know and I ...
-6
votes
0answers
36 views

Example of graph pebbling number and significance

According to the Wikipedia article on graph pebbling: Graph pebbling is a mathematical game and area of interest played on a graph with pebbles on the vertices. 'Game play' is composed of a ...
1
vote
1answer
42 views

What is $\langle I\rangle$ in this text?

I've read the following: It is easy to see that given any independent set $I$ in $V$, the vertices of $V-I$ form a covering of $G$. Conversely, if $V-I$ forms a covering, then $\langle I\rangle$ ...
1
vote
1answer
33 views

All the combination of cycles of consecutive numbers [on hold]

Let say that we have $N$ consecutive number $1,2,...,N$ and we want to find all the possible consecutive number cycles of length $2n+1$. For example: $$\begin{align}&N = 5\\&n = 3\ \ \ \ ...
0
votes
1answer
22 views

Randomized Algorithm for finding perfect matchings

I'm stuck on some of the theory in these notes, i'm trying to learn about randomized algorithms in general and am currently stuck on some notes regarding perfect matchings. Here is a link to the ...
2
votes
1answer
14 views

Relation between number of tree edges in graph with $n$ vertices and $k$ components.

It's a sort of given in my book without any proof that : $$t=n-k$$ where, $t$ = the number of tree edges $n$ = number of vertices $k$ = number of components. Can someone explain me the ...
5
votes
1answer
61 views

Almost every graph is asymmetric?

Here is a question: If i choose at random an isomorphism class of graph(no loops, undirected) on n vertices(with uniform probability on the set of such isomorphism classes), is the probability that ...
1
vote
1answer
24 views

Nearest neighbour algorithm (or so I think).

The algorithm is as follows: Given a graph, we start with some arbitrary vertex, in this vertex the path starts. From a vertex we are at we proceed to a neighbour vertex along some edge, we're keeping ...
1
vote
0answers
7 views

Show that a comparability graph is perfect.

Show that a comparability graph is perfect. I'm trying to be able to prove Dilworth's Theorem from perfect graphs. I'll cite the perfect graph theorem for the complement step. This is the part ...
2
votes
1answer
26 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 ...
1
vote
2answers
27 views

Complement of a bipartite graph

What constraint must be placed on a bipartite graph G to guarantee that G's complement will also be bipartite? I see someone saying that it can't be 4 or more in each group, but I don't see why. I ...
2
votes
1answer
30 views

Network Theorem

Our Electrical Engineering professor told us about this formula relating to circuits: $$Network \ Theorem: \ \ \ \ b = m+n-1$$ where $b$ = number of branches in circuit, $m$ = number of closed ...
0
votes
0answers
26 views

Clique cycles structure

I am currently going through the paper "Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles" by Peter Allen (http://www.ime.usp.br/~allen/twocycle.pdf) and I have some ...
2
votes
1answer
21 views

Difference of two graphs

Given two graphs $G_{1}$ and $G_{2}$ what exactly is the definition of $G_{1}-G_{2}$ used in the Diestel book? Most operations on graphs are clearly defined apart from this one.
0
votes
1answer
13 views

Spectral gap vs. algebraic connectivity

Can someone please clarify how the spectral gap of a graph relates to its algebraic connectivity (aka Fiedler value) and whether these use the adjacency matrix or laplacian matrix?
0
votes
0answers
8 views

Can anyone help to find an algorithm to change a randomly colored map to one where no same color is near using only swaping?

The main Codition is that only swaping color between states in allowed
0
votes
1answer
18 views

How many undirected graphs are possible with $4$ labelled vertices such that exactly $1$ edge is present?

I have drawn the graph and the result is $6$ graphs are possible. A simple graph can have a maximum of $\Large\binom{n}{2}$ edges and each edge can exist or not exist. Therefore, ...
2
votes
1answer
28 views

Chromatic number and vertex covering number

For any graph $G=(V,E)$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$. Let $\chi(G)$ denote the chromatic number of $G$. Is there a graph $G$ with $\tau(G) < \chi(G) - 1$?
0
votes
2answers
36 views

Discrete maths proving a random observation

Suppose you had 6 points. Each point can choose to either visit another point, or choose not to visit another point. However, it can't visit itself. In addition, visiting another point works in both ...
0
votes
0answers
22 views

Reference for the proof of interlacing of eigenvalues of submatrices

If one has a $n \times n$ Hermitian matrix $A$ and one removes $k$ of the rows and their corresponding columns then the eigenvalues of the remnant interlace the eigenvalues of the full matrix. Can ...
0
votes
0answers
15 views

How do I find point locations on a graph from edges and one known point position?

I have been given a collection of nodes and edges such that each node connects to every other node by an edge. All the edge lengths are known. One of the nodes locations (x,y) is known, but the rest ...
0
votes
2answers
18 views

Why does list coloring provides a more general setting to discuss the chromatic number?

I'm reading the Handbook of Graph Theory. It says the following: And a little before, the definitions of Chromatic Number: I don't understand what is this generality. Why the list ...
4
votes
3answers
69 views

Outline for high school combinatorics class?

I am a high school student and I have taken all the math classes that my school provides (through calculus AB). I have been looking at a possible independent study for next year and I have landed on ...
3
votes
2answers
66 views

Finite groups and topological spaces

Can we connect topological spaces with groups as: For topological space $X$ take biective homomorfisms $\phi: X\to X$, then divide such homomorphisms on classes of equivalency $\phi_1 \equiv\phi_2$ ...
2
votes
2answers
28 views

Matching Algorithm in Graph Theory

Given $n$ people, $k$ out of which own a car. We need to match a car for each person without a car. Conditions: Each car fits $5$ people, including the driver. Each driver will only allow his ...
1
vote
0answers
29 views

Are there any programs like family echo that I can use to map mathematics?

Family echo is an online program that allows one to make a family tree, if nothing is clicked it shows most of the family tree as it is, but if one clicks a name one can see clearly all the ancestors ...
0
votes
1answer
28 views

Factor of a Graph

Is $K_{2n}$ $2$-factorable? Illustrate with an example. $K_4$ is $2$-factorable but at many places it is generalized that $K_{2n}$ is not $2$-factorable. Is saying that a $2$-factor exists in a ...
-1
votes
0answers
23 views

Min. color $N$ if every $4$ vertex subgraph has a $3$ degree vertex [duplicate]

If a graph has $N$ vertices and every $4$ vertex subgraph has a $3$ degree vertex then prove there is a vertex with degree $N-1$.
2
votes
1answer
25 views

What is this binding function?

I'm reading the Handbook of Graph Theory. What is binding function (I mean, what function is it? $2x?$ $2x+x^2?$)? It says that it's a function $f:\mathbb{N}\to\mathbb{N}$ and it might have ...
2
votes
0answers
22 views

Check if graphs are Eulerian

I've been checking whether these graphs are Eulerian; I've come to conclusion that all of them are Eulerian, because they're all connected and all the vertices are of even degree. However, when I ...
3
votes
0answers
60 views

Combinatorics project ideas for high school students

It's that time again! Last year I asked for high school project ideas in the area of algebraic geometry, this year it's combinatorics (you can include graph theory and combinatorial game theory if you ...
2
votes
1answer
30 views

$3$-edge coloring of Georges Graph

Accoring to Wolfram|Alpha, Georges Graph $\hskip1in$ is 3-edge colorable. Does anybody have a actual 3-edge coloring in form of three sub-matrices of the adjacence matrix: $$A_1+A_2+A_3=A $$ I ...
1
vote
1answer
13 views

Proof by induction that for a complete simple and undirected graph that $|E|=\frac {n(n-1)} 2$

Prove with induction that for a complete simple and undirected graph that $|E|=\frac {n(n-1)} 2$ Base case is trivial. Suppose that for a graph with $n-1$ vertices we have $|E|=\frac ...
4
votes
0answers
22 views

Hamiltonian cycle and Euler Cycle. [duplicate]

When $G = K_n, n \ge 3$ and $n$ is odd, then from the edges of the $G$ can be built edge-disjoint Hamiltonian cycles. Is it true?